树链剖分学习笔记

树链剖分

树链剖分（树剖/链剖）有多种形式，如 重链剖分，长链剖分 和用于 Link/cut Tree 的剖分（有时被称作“实链剖分”），大多数情况下（没有特别说明时），“树链剖分”都指“重链剖分”。
引自：OI-WIKI

重链剖分

我们给出一些定义

• 定义 重子节点 表示其子节点中子树最大的子结点。如果有多个子树最大的子结点，取其一。如果没有子节点，就无重子节点。

• 定义 轻子节点 表示剩余的所有子结点。

• 从这个结点到重子节点的边为 重边。

• 到其他轻子节点的边为 轻边。

• 若干条首尾衔接的重边构成 重链。

简单来说，我们要做的就是把一颗树剖分成一条条链（如图左到图右）

具体点：我们把落单的结点也当作重链，那么我们要将整棵树就被剖分成若干条重链。

实现

分两个 DFS，所需变量：

fa[] : fa[i] 表示第 i 个节点的父亲节点；
Hson[] : Hson[i] 表示第 i 个节点的重儿子节点；
Dep[] : Dep[i] 表示第 i 个节点的深度（根节点深度为 1）；
Size[] : Size[i] 表示第 i 个节点的子树大小；
Top[] : Top[i] 表示第 i 个节点所在的链的顶部节点；
seg[] : seg[i] 表示第 i 个节点的 DFS 序；
rev[] : 表示 DFS 序所对应的节点编号。

CODE：

void Podfs1(int p, int f) {
	fa[p] = f;
	Dep[p] = Dep[f] + 1;
	Size[p] = 1;
	for (int i = head[p]; i; i = node[i].next) {
		int v = node[i].y;
		if (v == f) continue;
		Podfs1(v, p);
		Size[p] += Size[v];
		if (Size[v] > Size[Hson[p]]) Hson[p] = v;
	}
}

void Podfs2(int p, int top) {
	++DFNtot;
	Top[p] = top;
	seg[p] = DFNtot;
	rev[DFNtot] = p;
	if (Hson[p])
		Podfs2(Hson[p], top);
	for (int i = head[p]; i; i = node[i].next) {
		int v = node[i].y;
		if (v == fa[p]) continue;
		if (Hson[p] != v) Podfs2(v, v);
	}
}

配合线段树与实现 LCA：

P3384 【模板】重链剖分/树链剖分

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int _ = 1e5 + 7;

int N, M, P, R, val[_];
int fa[_], Hson[_], Dep[_], Size[_], Top[_], seg[_], rev[_], DFNtot = 0;

int head[_], Tot = 0;
struct Node {
	int y, next;
	Node() {next = 0;}
} node[2 * _];

void add(int x, int y) {
	++Tot;
	node[Tot].y = y;
	node[Tot].next = head[x];
	head[x] = Tot;
}

/*--树剖dfs--*/
void Podfs1(int p, int f) {
	fa[p] = f;
	Dep[p] = Dep[f] + 1;
	Size[p] = 1;
	for (int i = head[p]; i; i = node[i].next) {
		int v = node[i].y;
		if (v == f) continue;
		Podfs1(v, p);
		Size[p] += Size[v];
		if (Size[v] > Size[Hson[p]]) Hson[p] = v;
	}
}
void Podfs2(int p, int top) {
	++DFNtot;
	Top[p] = top;
	seg[p] = DFNtot;
	rev[DFNtot] = p;
	if (Hson[p])
		Podfs2(Hson[p], top);
	for (int i = head[p]; i; i = node[i].next) {
		int v = node[i].y;
		if (v == fa[p]) continue;
		if (Hson[p] != v) Podfs2(v, v);
	}
}
/*--线段树--*/
struct Tree {
	int l, r, sum;
	int lazy;
} tree[4 * _];

int lson(int root) {return root << 1;}
int rson(int root) {return root << 1 | 1;}

void Push_Up(int root) {
	tree[root].sum = (tree[lson(root)].sum + tree[rson(root)].sum) % P;
}

void Push_Down(int root) {
	if (tree[root].lazy != 0) {
		int num = tree[root].lazy;
		tree[lson(root)].sum = (tree[lson(root)].sum + (tree[lson(root)].r - tree[lson(root)].l + 1) * num % P) % P;
		tree[rson(root)].sum = (tree[rson(root)].sum + (tree[rson(root)].r - tree[rson(root)].l + 1) * num % P) % P;
		tree[lson(root)].lazy = (tree[lson(root)].lazy + num) % P;
		tree[rson(root)].lazy = (tree[rson(root)].lazy + num) % P;
		tree[root].lazy = 0;
	}
}

void Build(int l, int r, int root) {
	tree[root].l = l;
	tree[root].r = r;
	if (l == r) {
		tree[root].sum = val[rev[l]] % P;
		return ;
	}
	int mid = l + r >> 1;
	Build(l, mid, lson(root));
	Build(mid + 1, r, rson(root));
	Push_Up(root);
}

void Change(int root, int l, int r, int L, int R, int num) {
	if (L <= l && r <= R) {
		tree[root].sum += (r - l + 1) * num % P;
		tree[root].sum %= P;
		tree[root].lazy += num % P;
		tree[root].lazy %= P;
		return ;
	}
	Push_Down(root);
	int mid = l + r >> 1;
	if (L <= mid) 
		Change(lson(root), l, mid, L, R, num);
	if (mid < R)
		Change(rson(root), mid + 1, r, L, R, num);
	Push_Up(root);
	return ;
}

int Query(int root, int l, int r, int L, int R) {
	if (L > r || R < l) return 0;
	if (L <= l && r <= R) 
		return tree[root].sum % P;
	int ans = 0;
	Push_Down(root);
	int mid = l + r >> 1;
	if (L <= mid) {
		ans += Query(lson(root), l, mid, L, R) % P;
		ans %= P;
	}
	if (mid < R) {
		ans += Query(rson(root), mid + 1, r, L, R) % P;
		ans %= P;
	}
	return ans % P;
}

/*--LCA--*/
void TChange(int u, int v, int num) {
	while (Top[u] != Top[v]) {
		if (Dep[Top[u]] > Dep[Top[v]]) {
			Change(1, 1, DFNtot, seg[Top[u]], seg[u], num);
			u = fa[Top[u]];
		} else {
			Change(1, 1, DFNtot, seg[Top[v]], seg[v], num);
			v = fa[Top[v]];
		}
	}
	if (Dep[u] > Dep[v]) swap(u, v);
	Change(1, 1, DFNtot, seg[u], seg[v], num);
}
int TQuery(int u, int v) {
	int ans = 0;
	while (Top[u] != Top[v]) {
		if (Dep[Top[u]] > Dep[Top[v]]) {
			ans = ans + Query(1, 1, DFNtot, seg[Top[u]], seg[u]) % P;
			ans %= P;
			u = fa[Top[u]];
		} else {
			ans = ans + Query(1, 1, DFNtot, seg[Top[v]], seg[v]) % P;
			ans %= P;
			v = fa[Top[v]];
		}
	}
	if (Dep[u] > Dep[v]) swap(u, v);
	ans = (ans + Query(1, 1, DFNtot, seg[u], seg[v]) % P) % P;
	return ans;
}
signed main() {
	cin >> N >> M >> R >> P;
	for (int i = 1; i <= N; i++) cin >> val[i];
	for (int i = 1; i < N; i++) {
		int x, y;
		cin >> x >> y;
		add(x, y);
		add(y, x);
	}
	
	Podfs1(R, 0);
	Podfs2(R, R);
	
	Build(1, DFNtot, 1);
	
	while (M--) {
		int k;
		cin >> k;
		if (k == 1) {
			int x, y, z;
			cin >> x >> y >> z;
			TChange(x, y, z);
		} else if (k == 2) {
			int x, y;
			cin >> x >> y;
			cout << TQuery(x, y) << '\n';
		} else if (k == 3) {
			int x, z;
			cin >> x >> z;
			Change(1, 1, DFNtot, seg[x], seg[x] + Size[x] - 1, z);
		} else if (k == 4) {
			int x;
			cin >> x;
			cout << Query(1, 1, DFNtot, seg[x], seg[x] + Size[x] - 1) << '\n';
		}
	}
	return 0;
}