来解决树上DS问题。
因为没有能够直接高效维护树型结构的DS，于是把树剖分成链，然后拿序列上的DS去维护每一条链的信息。
树链剖分有很多种：轻重链剖分，长链剖分，虚实链剖分。
轻重链剖分
这里是轻重链剖分。常数很小。
其实不一定要用线段树维护，但用线段树维护是最常见的。
支持换根，路径修改，路径查询，子树修改，子树查询，查两点LCA。
钦定子树大小最大的儿子为当前节点\(u\)的重儿子\(son_u\)，其他儿子为轻儿子，连向重儿子的边称为重边，连向轻儿子的边称为轻边，重边连起来成为重链。
一些性质：
-
树上每个节点都属于且仅属于一条重链。
-
重链链顶一定不是重儿子，显然的。
-
剖分时重边优先遍历，那么一条重链中的\(dfn\)是连续的。\(dfn\)自身也有性质，一棵子树内的\(dfn\)是连续的。
-
任意一个节点到根节点的路径上最多经过\(\log n\)条轻边和重链，那么树上任意一条路径都可以被拆成\(\log n\)条轻边和重链。
维护路径信息
由于链上的\(dfn\)连续，那么就是维护区间信息，再让\(u,v\)两点不断往上跳。
用线段树一次是\(O(\log^2 n)\)的。
维护子树信息
子树内\(dfn\)连续，那么就是维护区间信息。
用线段树一次是\(O(\log n)\)的。
求LCA
两点不断沿着重链往上跳，当跳到同一条重链上时，深度较浅的是LCA。
向上跳重链时先跳重链顶端深度较深的。
是\(O(\log n)\)的。
换根
换根后的路径与子树操作
支持换根，路径赋值，查子树最小值。
\(Sol\)：
注意到路径赋值其实和换根没什么关系，直接做就行。
换根肯定不能真换根，不然会炸。
考虑换根后新根和当前查询的点\(x\)的关系，大力分讨：
-
新根是\(x\)，那么输出整棵树的答案。
-
新根在原树中不在\(x\)的子树内，那么\(x\)的子树答案不变。
-
新根在原树中在\(x\)的子树内，设新根在原树中\(x\)的儿子\(y\)的子树内，那么答案就是整棵树扣掉\(y\)的子树的答案。
如何求\(y\)？若新根不断向上跳重链可以跳到和\(x\)在同一条重链上，且仍在\(x\)的子树内，那么\(y=son_x\)。同时\(y\)也可能是\(x\)的轻儿子，此时\(y\)是一条重链的链顶，所以跳的时候不断判断当前所在重链的链顶的父亲是否是\(x\)即可。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+10;
const ll inf=0x7fffffff;
int n,m,tot=0,cnt=0,rt,head[maxn],id[maxn],dep[maxn],fa[maxn],son[maxn],tp[maxn],siz[maxn];
ll w[maxn],wt[maxn];
struct edge{
int v,nxt;
}e[maxn<<1];
inline void add(int u,int v){
e[++tot].v=v;
e[tot].nxt=head[u];
head[u]=tot;
}
struct TREE{
ll mi,tag;
}t[maxn<<1];
#define ls(k) k<<1
#define rs(k) k<<1|1
inline ll min(ll x,ll y){
return x<y?x:y;
}
inline void pushup(int k){
t[k].mi=min(t[ls(k)].mi,t[rs(k)].mi);
}
inline void pushdown(int k){
if(t[k].tag){
t[ls(k)].tag=t[rs(k)].tag=t[k].tag;
t[ls(k)].mi=t[rs(k)].mi=t[k].tag;
t[k].tag=0;
}
}
void build(int k,int l,int r){
if(l==r){
t[k].mi=wt[l];
return;
}
int mid=(l+r)>>1;
build(ls(k),l,mid);
build(rs(k),mid+1,r);
pushup(k);
return;
}
void update(int k,int l,int r,int ql,int qr,int v){
if(ql<=l&&r<=qr){
t[k].tag=t[k].mi=v;
return;
}
pushdown(k);
int mid=(l+r)>>1;
if(ql<=mid) update(ls(k),l,mid,ql,qr,v);
if(mid<qr) update(rs(k),mid+1,r,ql,qr,v);
pushup(k);
return;
}
ll query(int k,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr) return t[k].mi;
pushdown(k);
int mid=(l+r)>>1;
ll res=inf;
if(ql<=mid) res=min(res,query(ls(k),l,mid,ql,qr));
if(mid<qr) res=min(res,query(rs(k),mid+1,r,ql,qr));
pushup(k);
return res;
}
void dfs1(int u,int f){
fa[u]=f;
dep[u]=dep[f]+1;
son[u]=-1;
siz[u]=1;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].v;
if(v==f) continue;
dfs1(v,u);
siz[u]+=siz[v];
if(son[u]==-1||siz[son[u]]<siz[v]) son[u]=v;
}
}
void dfs2(int u,int p){
tp[u]=p;
id[u]=++cnt;
wt[id[u]]=w[u];
if(son[u]==-1) return;
dfs2(son[u],p);
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].v;
if(v==fa[u]||v==son[u]) continue;
dfs2(v,v);
}
}
void updline(int u,int v,int c){
while(tp[u]!=tp[v]){
if(dep[tp[u]]<dep[tp[v]]) swap(u,v);
update(1,1,n,id[tp[u]],id[u],c);
u=fa[tp[u]];
}
if(dep[u]>dep[v]) swap(u,v);
update(1,1,n,id[u],id[v],c);
}
int findson(int u,int v){
while(tp[u]!=tp[v]){
if(dep[tp[u]]<dep[tp[v]]) swap(u,v);
if(fa[tp[u]]==v) return tp[u];
u=fa[tp[u]];
}
if(dep[u]>dep[v]) swap(u,v);
return son[u];
}
ll qsubt(int u){
if(u==rt) return query(1,1,n,1,n);
if(id[u]>id[rt]||id[rt]>id[u]+siz[u]-1) return query(1,1,n,id[u],id[u]+siz[u]-1);
int sn=findson(rt,u);
ll res=min(query(1,1,n,1,id[sn]-1),id[sn]+siz[sn]<=n?query(1,1,n,id[sn]+siz[sn],n):inf);
return res;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<n;++i){
int u,v;
scanf("%d%d",&u,&v);
add(u,v);
add(v,u);
}
for(int i=1;i<=n;++i) scanf("%d",&w[i]);
scanf("%d",&rt);
dfs1(1,0);
dfs2(1,1);
build(1,1,n);
for(int i=1;i<=m;++i){
int opt;
scanf("%d",&opt);
if(opt==1){
int tmp;
scanf("%d",&tmp);
rt=tmp;
}
else if(opt==2){
int x,y,v;
scanf("%d%d%d",&x,&y,&v);
updline(x,y,v);
}
else if(opt==3){
int u;
scanf("%d",&u);
printf("%lld\n",qsubt(u));
}
}
return 0;
}
换根后的LCA
主要就是求换根后的LCA。
以下记\(lca(u,v)\)表示原树上的LCA，\(LCA(u,v)\)表示换根后的LCA，\(rt\)表示新根。
换根后求\(x,y\)的LCA需要大力分讨（以下默认\(dep_x\le dep_y\)）：
第一类：\(lca(x,y)=x\)时。即\(x,y\)在原树上时祖先后代关系。
-
\(rt\)在\(x\)的子树内也在\(y\)的子树内，那么\(LCA(x,y)=y\)。
-
\(rt\)在\(x\)的子树内却不在\(y\)的子树内，那么\(LCA(x,y)=lca(y,rt)\)。
-
\(rt\)不在\(x\)的子树内，那么\(LCA(x,y)=x\)。
第二类：\(lca(x,y)\ne x\)。即\(x,y\)在原树上在不同的子树中。
-
\(rt\)在\(x\)的子树内，那么\(LCA(x,y)=x\)；\(rt\)在\(y\)的子树内，那么\(LCA(x,y)=y\)。
-
\(rt\)在\(x\)到\(y\)的简单路径上，那么\(LCA(x,y)=rt\)。判断条件为\((lca(x,rt)=rt \&\&lca(y,rt)=lca(x,y))||(lca(y,rt)=rt\&\&lca(x,rt)=lca(x,y))\)，另一种用\(dep\)判断的写法是\((lca(x,rt)=rt\&\&dep_{rt}\ge dep_{lca(x,y)})||(lca(y,rt)=rt\&\&dep_{rt}\ge dep_{lca(x,y)})\)。
-
\(rt\)在\(lca(x,y)\)上方，那么\(LCA(x,y)=lca(x,y)\)。判断为\(lca(x,rt)=lca(y,rt)\)。
-
\(rt\)在\(x\)到\(y\)的路径上的点\(u\)子树中，那么\(LCA(x,y)=u\)。\(lca(x,rt)=lca(x,y)\)时，\(u=lca(y,rt)\)。\(lca(y,rt)=lca(x,y)\)时，\(u=lca(x,rt)\)。
分讨，爽！！！