网站 linux 服务器网片加工机器

树链剖分这玩意儿还挺重要的，是解决静态树问题的一个很好的工具~

这里主要介绍一下做题时经常遇到的两个操作：

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);
}