树链剖分简介
维护x节点到y节点的区间值，或得到树的各点的dep 各链的top 方便来求lca问题
原理
树剖是通过轻重边剖分将树分割成多条链，然后利用数据结构来维护这些链（本质上是一种优化暴力）
详解
首先明确概念：
重儿子：父亲节点的所有儿子中子树结点数目最多（size最大）的结点；
轻儿子：父亲节点中除了重儿子以外的儿子；
重边：父亲结点和重儿子连成的边；
轻边：父亲节点和轻儿子连成的边；
重链：由多条重边连接而成的路径；
轻链：由多条轻边连接而成的路径；
两个关键的dfs
(dfs1): 预处理siz son dep fa
(dfs2): 预处理id top rk wt
| 名称 | 含义 |
|---|---|
| (siz[u]) | 以u为根节点的树的大小 |
| (son[u]) | u的重儿子 |
| (dep[u]) | u的深度 |
| (fa[u]) | u的父亲节点 |
| (id[u]) | u的dfs序 |
| (top[u]) | u所在链的深度最小节点 |
| (wt[id]) | 新标号id对应的权重 |
| (rk[id]) | id对应的u |
dfs
void dfs1(int u)//预处理siz son dep fa
{
siz[u]=1;//包含u的子树
son[u]=0;
for(int i=0;i<g[u].size();i++)
{
int v=g[u][i];
if(v==fa[u])continue;
dep[v]=dep[u]+1;//更新子节点
fa[v]=u;
dfs1(v);
siz[u]+=siz[v];//更新v后,累加到u
if(siz[v]>siz[son[u]])son[u]=v;//更新重儿子
}
}
void dfs2(int u,int rt)//预处理id top rk
{
id[u]=++cnt;
//rk[index]=u;
wt[cnt]=w[u];
top[u]=rt;
if(son[u])dfs2(son[u],rt);//先搜重儿子
for(int i=0;i<g[u].size();i++)
{
int v=g[u][i];
if(v==fa[u]||v==son[u])continue;
dfs2(v,v);
}
}
维护树链
预处理过后要对链进行维护，因为每段链是连续的，一般选择线段树维护区间和，实现区间查询和区间更新，即将得到的(id[])和(wt[])进行建树
inline int qRange(int x,int y){
int ans=0;
while(top[x]!=top[y]){//当两个点不在同一条链上
if(dep[top[x]]<dep[top[y]])swap(x,y);//把x点改为所在链顶端的深度更深的那个点
res=0;
query(1,1,n,id[top[x]],id[x]);//ans加上x点到x所在链顶端 这一段区间的点权和
ans+=res;
ans%=mod;//按题意取模
x=fa[top[x]];//把x跳到x所在链顶端的那个点的上面一个点
}
//直到两个点处于一条链上
if(dep[x]>dep[y])swap(x,y);//把x点深度更深的那个点
res=0;
query(1,1,n,id[x],id[y]);//这时再加上此时两个点的区间和即可
ans+=res;
return ans%mod;
}
inline void updRange(int x,int y,int k){//同上
k%=mod;
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])swap(x,y);
update(1,1,n,id[top[x]],id[x],k);
x=fa[top[x]];
}
if(dep[x]>dep[y])swap(x,y);
update(1,1,n,id[x],id[y],k);
}
inline int qSon(int x){
res=0;
query(1,1,n,id[x],id[x]+siz[x]-1);//子树区间右端点为id[x]+siz[x]-1
return res;
}
inline void updSon(int x,int k){//同上
update(1,1,n,id[x],id[x]+siz[x]-1,k);
}
剩下的部分就是线段树了。
树链求lca
代码
inline int lca(int x,int y)
{
while(top[x]!=top[y])//从深的点向上跳，直到x和y在一条链上
{
if(dep[top[x]]<dep[top[y]])
swap(x,y);
x=fa[top[x]];
}
if(dep[x]>dep[y])swap(x,y);公共祖先即为链上深度浅的结点
return x;
}