我们发现：在树上维护一些信息不方便我们套用一些数据结构，但树链剖分可以将树分割为若干条链。树链剖分的方式有很多种，在算法竞赛中，应用最广泛的是重链剖分。 一般使用线段树维护。 定义： 重子节点为当前节点的所有儿子中子树最大的子节点，从这个节点到重子节点的边叫做重边，重边相连构成重链。与之对应地，有轻子节点，轻边。 image

树链剖分的实现使用了 2 遍 dfs，分别记录了不同信息。 ### dfs1 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void dfs1(int u,int f){
	dep[u]=dep[f]+1;//深度 
	siz[u]=1;//子树大小 
	fa[u]=f;//父节点 
	int maxson=-1;//子节点中最大的siz，也就是重儿子所对的siz 
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].to;
		if(v!=f){
			dfs1(v,u);
			siz[u]+=siz[v];
			if(siz[v]>maxson){
				son[u]=v;//重儿子 
				maxson=siz[v];
			}
		}
	}
	return;
}
这里，维护了每个节点的深度，父节点和子树大小最大的子节点。 ### dfs2 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
void dfs2(int u,int topf){
	dfn[u]=++cnt;//dfn序，也就是线段树上的编号 
	top[u]=topf;//当前树链的最顶端节点 
	w1[cnt]=w[u];//新的权值 
	if(!son[u])
		return;
	dfs2(son[u],topf);//重儿子的处理 
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].to;
		if(v!=fa[u]&&v!=son[u])//轻儿子的处理 
			dfs2(v,v);
	}
	return;
}
这里，维护了每个节点的 dfn，每个节点所在重链的链顶和使用 dfn 编号的点权。 使用 dfn 的原因是 dfn 可以保证同一子树内的点在一个连续的区间内，方便使用数据结构进行维护。

查询操作

树链剖分完毕后，我们就可以借助数据结构求任意点 \(x\) 的子树的相关信息。 例如，查询子树所有节点权值之和。 

1
2
3
//维护区间和的线段树
scanf("%d",&x);
printf("%d\n",query(1,1,n,dfn[x],dfn[x]+siz[x]-1));
可以证明，\(x\) 的子树所对的区间是 \(x\) 的 dfn 到 \(x\) 的 dfn 加 \(x\) 的子树大小减 \(1\)。

树链剖分还有一个强大的功能：求 LCA。 不断向上跳重链，当跳到同一条重链上时，深度较小的结点即为 LCA。 向上跳重链时需要先跳所在重链顶端深度较大的那个。 

1
2
3
4
5
6
7
8
9
int lca(int u,int v){
	while(top[u]!=top[v]){
		if(dep[top[u]]>dep[top[v]])
			u=fa[top[u]];
		else
			v=fa[top[v]];
	}
	return dep[u]>dep[v]?v:u;
}
类似地，我们就可以对任意点 \(x\) 到 \(y\) 路径上的点权进行查询和修改。 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int tree_sum(int x,int y){//x到y路径上的和 
	int ans=0;
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]])
			std::swap(x,y);
		ans=(ans+query(1,1,n,dfn[top[x]],dfn[x]))%p;
		x=fa[top[x]];//跳到链顶的父节点 
	}
	if(dep[x]>dep[y])
		std::swap(x,y);
	ans=(ans+query(1,1,n,dfn[x],dfn[y]))%p;
	return ans;
}
void tree_add(int x,int y,int k){//x到y最短路径上所有节点值加k 
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]])
			std::swap(x,y);
		modify(1,1,n,dfn[top[x]],dfn[x],k);
		x=fa[top[x]];
	}
	if(dep[x]>dep[y])
		std::swap(x,y);
	modify(1,1,n,dfn[x],dfn[y],k);
	return;
}
*注：对 \(p\) 取模是题目要求。

如果边权下放点权维护边信息，不想累加 LCA 处的贡献，可以这么写： 

1
2
3
4
5
6
7
8
9
10
11
12
int ask(int x,int y){
    int res=0;
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]])
            swap(x,y);
        res+=query(dfn[top[x]],dfn[x]);
        x=fa[top[x]];
    }
    if(dep[x]>dep[y]) swap(x,y);
    if(x!=y) res+=query(dfn[x]+1,dfn[y]);
    return res;
}

树链剖分的复杂度为 \(O(\log n)\)。而且一般情况下跑不满且常数极小。

模板

参考资料