树链剖分这玩意儿还挺重要的,是解决静态树问题的一个很好的工具~
这里主要介绍一下做题时经常遇到的两个操作:
1.在线求LCA
int LCA(int x,int y){
while(top[x]!=top[y])
if(dep[top[x]]>dep[top[y]]) x=fa[top[x]];
else y=fa[top[y]];
return dep[x]<dep[y]?x:y;
}
这个非常重要!!!
在很多题目中,我们需要借助LCA 来解题
2.换根操作
换一个根就重新剖一次当然是不现实的
不妨就先以1号节点为根剖一下
树链修改值当然直接按照重链在线段树上改就好了
主要就是讨论以x为根的子树对于不同的根时的dfn序范围
那么设当前的根是root
①:x==root:范围当然就是全局
②:x不在1到root的链上,在其他的支叉上:root为根或是1为根没有影响,
按普通套路来,即范围是[dfn[x],dfn[x]+size[x]-1]
图中蓝色的标号就是根据轻重链剖分进行的树上节点再标号id,红色笔迹标出的每一条树链就是一条重链,可以根据这个图来感性理解一下x不在1到root链上时的范围为什么不变
③:x在1到root的链上:这就是要处理的重点了
上图中紫色圈出的节点即是当前root,绿色圈出的节点即是要查询的子树的根x,那么可以看出当前x在1到root的链上。思考现在x的子树,其实就是除去x往root方向的那个子树外,所有的节点
int query_son(int x){
if(root==x) return st[1];
if(LCA(x,root)==x){
int ans=2147483647,from;
for(int i=head[x];i!=-1;i=edge[i].nxt)
if(LCA(edge[i].v,root)==edge[i].v){
from=edge[i].v;
break;
}
if(tid[from]>1) ans=min(ans,query(1,1,n,1,tid[from]-1));
if(tid[from]+size[from]<=n) ans=min(ans,query(1,1,n,tid[from]+size[from],n));
return ans;
}
return query(1,1,n,tid[x],tid[x]+size[x]-1);
}