树链剖分模板

• 2018-04-09
• 0
• 0

树链剖分，一般特指轻重链剖分 (Heavy-light decomposition)，是一种将树划分为链集的启发式剖分方法。

首先定义以下概念：

1. 子树大小：以某一节点为根节点的子树中节点的总数。子树大小与边权无关。
2. 重儿子 (重节点) ：在所有兄弟节点中，子树大小最大的节点。
3. 轻儿子 (轻节点) ：所有非重儿子节点。特殊地，根节点也被视作轻儿子。
4. 重链：由轻节点为链头，层层连向重儿子所形成的链。

如上图，标有红点的是轻儿子，同时必定为某条重链的链头。另外，加粗的边所连成的是重链。

轻重链剖分算法主要步骤是进行两次 DFS 预处理，然后使用线段树等数据结构维护重链和子树。

第一次 DFS 预处理出深度 dep[]，父节点 fa[]，子树大小 sz[] 以及重儿子 hson[]。第二次则预处理出 DFS 序 dfn[]，节点在线段树上对应的位置 id[] 以及所在重链链头 top[]。

在第二次 DFS 中有一个非常关键的步骤，就是先 DFS 重儿子，这样就可以保证重链上节点的 DFS 序连续。

然后我们可以发现修改子树时可以直接线段树上区间修改。修改路径则可模仿倍增求 LCA 的思想，将较深点往上跳到重链链头，同时线段树上区间修改该重链上节点信息，直到两个节点跳到一起为止。查询操作同理。

模板题为 洛谷 3384 【模板】树链剖分。

Code: O(NlogN+Mlog²N) [15664K, 436MS]

// 树链剖分 (2018.3.6)
// 洛谷 3384 【模板】树链剖分 
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#define MAXN 100005
#define MAXM 200005
using namespace std;

inline void getint(int &num){
	char ch;
	while(!isdigit(ch = getchar()));
	num = ch - '0';
	while(isdigit(ch = getchar())) num = num * 10 + ch - '0';
}

int N, M, R, P, w[MAXN];
int sum[MAXN << 2], addf[MAXN << 2];
#define lc (u << 1)
#define rc (u << 1 | 1)
int dep[MAXN], fa[MAXN], sz[MAXN], hson[MAXN], tope = 0;
int dfn[MAXN], dfstime = 0, top[MAXN], id[MAXN];

inline void update(int u) {sum[u] = (sum[lc] + sum[rc]) % P;}

inline void pushdown(int u, int l, int r){
	if(addf[u]){
		int mid = l + r >> 1;
		sum[lc] = (sum[lc] + (mid - l + 1) * addf[u]) % P, addf[lc] = (addf[lc] + addf[u]) % P;
		sum[rc] = (sum[rc] + (r - mid) * addf[u]) % P, addf[rc] = (addf[rc] + addf[u]) % P;
		addf[u] = 0;
	}
}

inline void build(int u, int l, int r){
	if(l == r) {sum[u] = w[id[l]] % P; return;}
	int mid = l + r >> 1;
	if(l <= mid) build(lc, l, mid);
	if(mid < r) build(rc, mid + 1, r);
	update(u);
}

inline void add(int u, int l, int r, int al, int ar, int v){
	if(l == al && r == ar) {sum[u] = (sum[u] + v * (r - l + 1)) % P, addf[u] = (addf[u] + v) % P; return;}
	pushdown(u, l, r);
	int mid = l + r >> 1;
	if(ar <= mid) add(lc, l, mid, al, ar, v);
	else if(al > mid) add(rc, mid + 1, r, al, ar, v);
	else add(lc, l, mid, al, mid, v), add(rc, mid + 1, r, mid + 1, ar, v);
	update(u);
}

inline int query(int u, int l, int r, int ql, int qr){
	if(l == ql && r == qr) return sum[u];
	pushdown(u, l, r);
	int mid = l + r >> 1;
	if(qr <= mid) return query(lc, l, mid, ql, qr);
	else if(ql > mid) return query(rc, mid + 1, r, ql, qr);
	else return (query(lc, l, mid, ql, mid) + query(rc, mid + 1, r, mid + 1, qr)) % P;
}

struct Edge{
	int np;
	Edge *nxt;
} *V[MAXN], E[MAXM];

inline void addedge(int u, int v) {E[++tope].np = v, E[tope].nxt = V[u], V[u] = &E[tope];}

inline void dfs1(int u, int f, int d){
	dep[u] = d, fa[u] = f, sz[u] = 1, hson[u] = 0;
	for(register Edge *ne = V[u]; ne; ne = ne->nxt){
		if(ne->np == f) continue;
		dfs1(ne->np, u, d + 1);
		sz[u] += sz[ne->np];
		if(sz[ne->np] > sz[hson[u]]) hson[u] = ne->np;
	}
}  // 第一次 dfs: 预处理深度 dep, 父节点 fa, 子树大小 sz 和重儿子 hson 

inline void dfs2(int u, int tp){
	dfn[u] = ++dfstime, id[dfstime] = u, top[u] = tp;
	if(!hson[u]) return;
	dfs2(hson[u], tp);  // 先 dfs 重儿子, 保证重链的 dfs 序连续 
	for(register Edge *ne = V[u]; ne; ne = ne->nxt)
		if(ne->np != fa[u] && ne->np != hson[u]) dfs2(ne->np, ne->np);
}  // 第二次 dfs: 预处理 dfs 序 dfn, 线段树上对应位置 id, 所在重链链头 top 

inline void path_add(int u, int v, int w){
	w %= P;
	while(top[u] != top[v]){
		if(dep[top[u]] < dep[top[v]]) swap(u, v);
		add(1, 1, N, dfn[top[u]], dfn[u], w);
		u = fa[top[u]];
	}
	if(dep[u] > dep[v]) swap(u, v);
	add(1, 1, N, dfn[u], dfn[v], w);
}

inline int path_query(int u, int v){
	int res = 0;
	while(top[u] != top[v]){
		if(dep[top[u]] < dep[top[v]]) swap(u, v);
		res = (res + query(1, 1, N, dfn[top[u]], dfn[u])) % P;
		u = fa[top[u]]; 
	}
	if(dep[u] > dep[v]) swap(u, v);
	res = (res + query(1, 1, N, dfn[u], dfn[v])) % P;
	return res;
}

inline void subtree_add(int u, int w) {add(1, 1, N, dfn[u], dfn[u] + sz[u] - 1, w);}

inline int subtree_query(int u) {return query(1, 1, N, dfn[u], dfn[u] + sz[u] - 1);}

int main(){
	getint(N), getint(M), getint(R), getint(P);
	for(register int i = 1; i <= N; i++) getint(w[i]);
	for(register int i = 1; i < N; i++){
		int u, v; getint(u), getint(v);
		addedge(u, v), addedge(v, u);
	}
	dfs1(R, 0, 1), dfs2(R, R);
	build(1, 1, N);
	while(M--){
		int opt, x, y, z; getint(opt);
		if(opt == 1) getint(x), getint(y), getint(z), path_add(x, y, z);
		else if(opt == 2) getint(x), getint(y), printf("%d\n", path_query(x, y));
		else if(opt == 3) getint(x), getint(z), subtree_add(x, z);
		else if(opt == 4) getint(x), printf("%d\n", subtree_query(x));
	}
	return 0;
}