本文的树链剖分指的是长链剖分
Part 1：知识点
树链剖分常用于解决下面的问题：
-
修改树上两点之间的路径上所有点的值。
-
查询树上两点之间的路径上节点权值的和/极值/其它（在序列上可以用数据结构维护，便于合并的信息）。
下面给出一些定义：
-
重儿子：表示一个节点的子节点中子树最大的子节点。如果有多个子树最大的子节点，取其一。如果没有子节点，就无重子节点。
-
轻儿子：表示剩余的所有子节点。
-
重边：连接一个节点与其重儿子的边。
-
轻边：除重边之外的边。
-
重链：若干条重边相连形成的链。
-
重边：若干条轻边相连形成的链。
实现
给出一些变量名：
-
\(fa[x]\)：表示节点 \(x\) 在树上的父亲
-
\(dep[x]\)：表示节点 \(x\) 在树上的深度。
-
\(siz[x]\) 表示节点 \(x\) 的子树的节点个数。
-
\(son[x]\) 表示节点 \(x\) 的重儿子。
-
\(top[x]\) 表示节点 \(x\) 所在重链的顶部节点（深度最小）。
-
\(dfn[x]\) 表示节点 \(x\) 的 \(dfn\) 序，也是其在线段树中的编号。
-
\(num[x]\) 表示 \(dfn\) 序所对应的节点编号，有 \(num[dfn[x]]=x\)。
树链剖分的实现分为两个 \(\rm dfs\) 的过程：
- 第一个 \(\rm dfs\)：求出 \(fa[x],dep[x],siz[x],son[x]\)
void dfs1(int x,int f)
{
son[x]=-1; siz[x]=1;
dep[x]=dep[f]+1; fa[x]=f;
for(int i=0; i<g[x].size(); i++)
{
int y=g[x][i];
if(y==f)
continue;
dfs1(y,x);
siz[x]+=siz[y];
if(son[x]==-1 || siz[y]>siz[son[x]])
son[x]=y;
}
}
//在main函数中
dfs1(rt,0);
- 第二个 \(\rm dfs\)：求出 \(top[x],dfn[x],num[x]\)
void dfs2(int x,int t)
{
top[x]=t;
dfn[x]=++dfn[0];
num[dfn[x]]=x;
if(son[x]==-1)
return;
dfs2(son[x],t);
for(int i=0; i<g[x].size(); i++)
{
int y=g[x][i];
if(y!=son[x] && y!=fa[x])
dfs2(y,y);
}
}
//在main函数中
dfs2(rt,rt);
求出上述变量后，我们可以将树上的每个点依照它们的 \(dfn\) 序映射到区间上，再在区间上建立线段树，即可完成许多操作
一些性质
-
树上每个节点都属于且仅属于一条重链。
-
重链开头的结点不一定是重子节点（因为重边是对于每一个结点都有定义的）。
-
重链内的 \(dfn\) 序是连续的。
-
一颗子树内的 \(dfn\) 序是连续的。
-
若边 \((x,y)\) 是轻边，则 \(size[y]\leq \dfrac{size[x]}{2}\)
因此，对于树上的任意一条路径，把它拆分成从 \(lca\) 分别向两边往下走，分别最多走 \(O(\log n)\) 次，因此，树上的每条路径都可以被拆分成不超过 \(O(\log n)\) 条重链。
Part 2：一些习题
P3384 【模板】重链剖分/树链剖分
要求支持下列操作：
-
1 x y z，表示将树从 \(x\) 到 \(y\) 结点最短路径上所有节点的值都加上 \(z\)。 -
2 x y，表示求树从 \(x\) 到 \(y\) 结点最短路径上所有节点的值之和。 -
3 x z，表示将以 \(x\) 为根节点的子树内所有节点值都加上 \(z\)。 -
4 x，表示求以 \(x\) 为根节点的子树内所有节点值之和。
操作 \(3,4\) 是典型的树链剖分维护子树。由于子树内的 \(dfn\) 序连续，所以直接在区间 \([dfn[x],dfn[x]+siz[x]-1]\) 上进行线段树的区间加和区间查询操作即可
操作 \(1,2\) 则是树链剖分维护两点路径。由于重链上的 \(dfn\) 序连续，所以每次操作选择深度大的链往上跳，跳的过程中 \(O(\log n)\) 地在线段树上更新，直到两点在同一条链为止。单次操作时间复杂度 \(O(\log^2 n)\)
void update(int x,int y,int v) //操作1
{
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]])
swap(x,y);
change(1,1,n,dfn[top[x]],dfn[x],v);
x=fa[top[x]];
}
if(dep[x]>dep[y])
swap(x,y);
change(1,1,n,dfn[x],dfn[y],v);
}
int query(int x,int y) //操作2
{
int val=0;
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]])
swap(x,y);
(val+=ask(1,1,n,dfn[top[x]],dfn[x]))%=mod;
x=fa[top[x]];
}
if(dep[x]>dep[y])
swap(x,y);
(val+=ask(1,1,n,dfn[x],dfn[y]))%=mod;
return val;
}
P2146 [NOI2015] 软件包管理器
下载则将 \(x\) 到根路径上的所有点赋值成 \(1\)
卸载则将 \(x\) 子树内所有的点赋值成 \(0\)
输出操作前后 \(1\) 的变化量即可
P2590 [ZJOI2008] 树的统计
变成单点修改+区间查询区间和/最大值，不用写懒标记还更简单
P2486 [SDOI2011] 染色
记录四个参数：区间前缀颜色，后缀颜色，颜色段数量、懒标记
合并两个区间时若左区间的后缀等于右区间的前缀就 \(-1\)
但是这样仍有问题，就是在树剖跳链时无法减去链与链之间的重复计算。考虑在调用线段树函数时顺便记录区间左端点和右端点的颜色，在跳链时进行去重
int ask(int p,int l,int r,int ql,int qr)
{
if(l==ql)
lcc=lc(p);
if(r==qr)
rcc=rc(p);
if(ql<=l && qr>=r)
return sum(p);
spread(p);
int mid=(l+r)>>1,val=0;
if(ql<=mid)
val+=ask(p*2,l,mid,ql,qr);
if(qr>mid)
val+=ask(p*2+1,mid+1,r,ql,qr);
return val-(ql<=mid && qr>mid? (rc(p*2)==lc(p*2+1)):0);
}
int query(int x,int y)
{
int val=0,xc=0,yc=0;
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]])
swap(x,y),swap(xc,yc);
val+=ask(1,1,n,dfn[top[x]],dfn[x]);
x=fa[top[x]];
if(xc==rcc)
val--;
xc=lcc;
}
if(dep[x]>dep[y])
swap(x,y),swap(xc,yc);
val+=ask(1,1,n,dfn[x],dfn[y]);
if(xc==lcc)
val--;
if(yc==rcc)
val--;
return val;
}
P3313 [SDOI2014] 旅行
一个宗教开一棵线段树，动态开点即可
P5838 [USACO19DEC] Milk Visits G
同上一题一样，一种奶牛开一棵线段树，查询和是否大于 \(0\) 即可
P4374 [USACO18OPEN] Disruption P
蕴含一些技巧（套路）的题目
首先发现对于每条树边去匹配额外边不好搞，所以反向考虑每条额外边对于树边的贡献。显然一条额外边 \((x,y)\) 可以对 \(x\) 到 \(y\) 简单路径上的所有边造成贡献，线段树维护即可
在线段树操作时，还需要边权转点权，一个经典套路是将每条边都转化到儿子上。具体操作时要注意一些小细节，详见代码
void update(int x,int y,int z)
{
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]])
swap(x,y);
change(1,1,n,dfn[top[x]],dfn[x],z);
x=fa[top[x]];
}
if(dep[x]>dep[y])
swap(x,y);
change(1,1,n,dfn[son[x]],dfn[y],z); //这里是关键一步
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1; i<n; i++)
{
scanf("%d%d",&u[i],&v[i]);
g[u[i]].push_back(v[i]);
g[v[i]].push_back(u[i]);
}
dfs1(1,0);
dfs2(1,1);
build(1,1,n);
for(int i=1; i<=m; i++)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
update(x,y,z);
}
for(int i=1; i<n; i++)
{
int x=max(dfn[u[i]],dfn[v[i]]); //找儿子
int ans=ask(1,1,n,x);
if(ans==INF)
printf("-1\n");
else
printf("%d\n",ans);
}
return 0;
}