树链剖分-重链剖分

发表于 更新于 分类于 ， 本文字数： 3.4k 阅读时长 ≈ 12 分钟
树链剖分的基本原理与实现流程, 主要是重链剖分.

重链剖分

是指一种对树进行划分的算法, 它先通过轻重边剖分（Heavy-Light Decomposition）将树分为多条链, 保证每个点属于且只属于其中一条链, 然后再通过数据结构（树状数组、SBT、SPLAY、线段树等）来维护每一条链.

定义

size[i] 以结点i为根的子树中结点的个数.
son[i] 结点i的重儿子.
dep[i] 结点i的深度, 根的深度为1.
top[i] 结点i所在重链的链首结点.
fa[i] 结点i的父结.
dfn[i] 在DFS找重链的过程中为结点i重新编的号码, 每条重链上的结点编号是连续的.
rnk[i] 链上节点对应的树上节点编号, 用于访问初值.

那么, 令 $V$ 是 $U$ 的儿子节点中size值最大的节点, 称 $V$ 是 $U$ 的重儿子重边, 除此之外, 所有的边称为轻边. 全部由重边构成的路径称为重链.

预处理

  1. 第一次DFS（预处理）
    从根节点出发, 递归遍历整棵树, 计算每个节点的size、dep、fa, 并找出每个节点的重儿子son（即子树最大的儿子）.

  2. 第二次DFS（分配编号）
    再次从根节点出发, 优先遍历重儿子, 将每个节点分配一个新的编号dfn, 并确定每个节点所在重链的链首top.

代码示例

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
26
27
28
29
30
31
void dfs1(int u, int f) {
    size[u] = 1;
    for (int i = head[u]; i; i = nxt[i]) {
        int v = to[i];
        if (v == f) continue;
        dep[v] = dep[u] + 1;
        fa[v] = u;
        dfs1(v, u);
        size[u] += size[v];
        if (size[v] > size[son[u]]) {
            son[u] = v;
        }
    }
}
void dfs2(int u, int t) {
    top[u] = t;
    dfn[u] = ++tot;
    rnk[tot] = u;
    if (!son[u]) return;
    dfs2(son[u], t);
    for (int i = head[u]; i; i = nxt[i]) {
        int v = to[i];
        if (v != fa[u] && v != son[u]) {
            dfs2(v, v);
        }
    }
}

// in int main()
dfs1(rt,0);
dfs2(rt,rt);

常见操作

单点处理

要处理 x 节点上的值, 直接访问 dfn[x] 即可.

路径上维护

由于链上的 dfn 都是连续的, 可以用线段树/树状数组直接维护这些重链.

但是大多数时间任意两个节点形成的路径并不是一条链. 我们的目标是让这两个节点到同一个重链上以便我们维护. 让 dep[top] 更大的节点往上跳到top, 同时修改这一段重链, 直到两个点到同一个重链上. 到同一重链后也要操作一下.

注意, 上述操作应跳至fa[top[x]],修改dfn[top[x]] ~ dfn[x], 以便跳到靠上一条的链.

对于边权转点权, 应当注意在最后一次操作时不能对lca操作, 其对应的边并不在操作的路径上.

参考代码

正常点权:

1
2
3
4
5
6
7
8
9
int ans = 0;
while (top[u] != top[v]) {
    if (dep[top[u]] < dep[top[v]]) swap(u, v);
    ans += ask(1, 1, n, dfn[top[u]], dfn[u]);
    u = fa[top[u]];
}
if (dep[u] > dep[v]) swap(u, v);
ans += ask(1, 1, n, dfn[u], dfn[v]);
return ans;

边权转点权:

1
2
3
4
5
6
7
8
9
10
11
int sum = 0;
while (top[u] != top[v]) {
    if (dep[top[u]] < dep[top[v]]) swap(u, v);
    sum += ask(1, 1, n, dfn[top[u]], dfn[u]);
    u = fa[top[u]];
}
if (dep[u] > dep[v]) swap(u, v);
sum += ask(1, 1, n, dfn[son[u]], dfn[v]);
// 也可以选择以下等价方案
ans += ask(1, 1, n, dfn[u], dfn[v]);
ans -= ask(1, 1, n, dfn[u], dfn[u]);

子树上维护

由dfs2的编号过程可知, 一个子树的dfn值使连续的. 由此可知, 我们可以直接对一个子树进行更改. 更改范围: $dfn_x \sim dfn_x+size[x]-1$

例题

例题 P2590 [ZJOI2008] 树的统计

按照题意维护即可

完整代码

 
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
#include <algorithm>
#include <iostream>
using namespace std;
const int N = 5e5 + 5;
int head[N], nxt[2 * N], to[2 * N], num = 0;
void add(int x, int y) {
    num++;
    to[num] = y;
    nxt[num] = head[x];
    head[x] = num;
}
int size[N], son[N], dep[N], top[N], fa[N], pos[N], rev[N];
void dfs1(int x, int f) {
    size[x] = 1;
    dep[x] = dep[f] + 1;
    fa[x] = f;
    son[x] = 0;
    for (int i = head[x]; i; i = nxt[i]) {
        int v = to[i];
        if (v == f) continue;
        dfs1(v, x);
        size[x] += size[v];
        if (size[v] > size[son[x]]) {
            son[x] = v;
        }
    }
}
int label = 0;
void dfs2(int x, int ance) {
    pos[x] = ++label;
    rev[label] = x;
    top[x] = ance;
    if (son[x]) dfs2(son[x], ance);
    for (int i = head[x]; i; i = nxt[i]) {
        int v = to[i];
        if (v == fa[x] || v == son[x]) continue;
        dfs2(v, v);
    }
}

int a[N], tree1[4 * N], tree2[4 * N];  // tree1 max tree2 sum
void build(int p, int l, int r) {
    if (l == r) {
        tree1[p] = tree2[p] = a[rev[l]];
        return;
    }
    int mid = (l + r) / 2;
    build(p * 2, l, mid);
    build(p * 2 + 1, mid + 1, r);
    tree1[p] = max(tree1[p * 2], tree1[p * 2 + 1]);
    tree2[p] = tree2[p * 2] + tree2[p * 2 + 1];
}
void change(int p, int l, int r, int x, int y) {
    if (l == r) {
        tree1[p] = y;
        tree2[p] = y;
        return;
    }
    int mid = (l + r) / 2;
    if (x <= mid)
        change(p * 2, l, mid, x, y);
    else
        change(p * 2 + 1, mid + 1, r, x, y);
    tree1[p] = max(tree1[p * 2], tree1[p * 2 + 1]);
    tree2[p] = tree2[p * 2] + tree2[p * 2 + 1];
}
int askmax(int p, int l, int r, int x, int y) {
    if (x <= l && r <= y) {
        return tree1[p];
    }
    int mid = (l + r) / 2;
    int ans = -1e9;
    if (x <= mid) ans = max(ans, askmax(p * 2, l, mid, x, y));
    if (mid + 1 <= y) ans = max(ans, askmax(p * 2 + 1, mid + 1, r, x, y));
    return ans;
}
int asksum(int p, int l, int r, int x, int y) {
    if (x <= l && r <= y) {
        return tree2[p];
    }
    int mid = (l + r) / 2;
    int ans = 0;
    if (x <= mid) ans += asksum(p * 2, l, mid, x, y);
    if (mid + 1 <= y) ans += asksum(p * 2 + 1, mid + 1, r, x, y);
    return ans;
}
int qmax(int u, int v, int n) {
    int ans = -1e9;
    while (top[u] != top[v]) {
        if (dep[top[u]] < dep[top[v]]) swap(u, v);
        ans = max(ans, askmax(1, 1, n, pos[top[u]], pos[u]));
        u = fa[top[u]];
    }
    if (dep[u] > dep[v]) swap(u, v);
    ans = max(ans, askmax(1, 1, n, pos[u], pos[v]));
    return ans;
}
int qsum(int u, int v, int n) {
    int ans = 0;
    while (top[u] != top[v]) {
        if (dep[top[u]] < dep[top[v]]) swap(u, v);
        ans += asksum(1, 1, n, pos[top[u]], pos[u]);
        u = fa[top[u]];
    }
    if (dep[u] > dep[v]) swap(u, v);
    ans += asksum(1, 1, n, pos[u], pos[v]);
    return ans;
}
int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n - 1; i++) {
        int u, v;
        cin >> u >> v;
        add(u, v);
        add(v, u);
    }
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    dfs1(1, 0);
    dfs2(1, 1);
    build(1, 1, n);
    int q;
    cin >> q;
    while (q--) {
        string op;
        int u, v;
        cin >> op >> u >> v;
        if (op == "CHANGE") {
            change(1, 1, n, pos[u], v);
        } else if (op == "QMAX") {
            cout << qmax(u, v, n) << endl;
        } else {
            cout << qsum(u, v, n) << endl;
        }
    }
    return 0;
}

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

这是一道正常的点权题, 有区间修改.

完整代码

 
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
#include <iostream>
#include <algorithm>
using namespace std;
const int N=100005;
int n,m,r,p;
int v[N];//节点初值
int size[N],dep[N],fa[N],son[N],top[N],id[N],rev[N];
int head[N],nxt[N*2],to[N*2],a[N*2];
int num=0,tot=0;
void add(int f,int t) {
	num++;
	to[num]=t;
	nxt[num]=head[f];
	head[f]=num;
}
void dfs1(int u,int f) {
	size[u]=1;
	for(int i=head[u]; i; i=nxt[i]) {
		int v=to[i];
		if(v==f)continue;
		dep[v]=dep[u]+1;
		fa[v]=u;
		dfs1(v,u);
		size[u]+=size[v];
		if(size[v]>size[son[u]]) {
			son[u]=v;
		}
	}
}
void dfs2(int u,int t) {
	top[u]=t;
	id[u]=++tot;
	rev[tot]=u;
	a[tot]=v[u];
	if(!son[u]) return;
	dfs2(son[u],t);
	for(int i=head[u]; i; i=nxt[i]) {
		int v=to[i];
		if(v!=fa[u]&&v!=son[u]) {
			dfs2(v,v);
		}
	}
}

int Tree[N*4],lazy[N*4];
void build(int pos,int l,int r) {
	if(l==r) {
		Tree[pos]=a[l]%p;
		return;
	}
	int mid=(l+r)/2;
	build(pos*2,l,mid);
	build(pos*2+1,mid+1,r);
	Tree[pos]=((long long)Tree[pos*2]+Tree[pos*2+1])%p;
}
void Lazy(int pos,int l,int r,int k) {
	lazy[pos]=(lazy[pos]+k)%p;
	Tree[pos]=(Tree[pos]+k*(r-l+1))%p;
}
void pushdown(int pos,int l,int r) {
	if(!lazy[pos]) return;
	int mid=(l+r)/2;
	Lazy(pos*2,l,mid,lazy[pos]);
	Lazy(pos*2+1,mid+1,r,lazy[pos]);
	lazy[pos]=0;
}
int query(int pos,int l,int r,int x,int y) {
	if(y<l||x>r) return 0;
	if(x<=l&&r<=y) {
		return Tree[pos];
	}
	int mid=(l+r)/2;
	pushdown(pos,l,r);
	return ((long long)query(pos*2,l,mid,x,y)+query(pos*2+1,mid+1,r,x,y))%p;
}
void change(int pos,int l,int r,int x,int y,int k) {
	if(x<=l&&r<=y) {
		Lazy(pos,l,r,k);

		return;
	}
	int mid=(l+r)/2;
	pushdown(pos,l,r);
	if(x<=mid) change(pos*2,l,mid,x,y,k);
	if(mid<y) change(pos*2+1,mid+1,r,x,y,k);
	Tree[pos]=(Tree[pos*2]+Tree[pos*2+1])%p;
}

int main() {
	cin>>n>>m>>r>>p;
	for(int i=1; i<=n; i++) {
		cin>>v[i];
	}
	for(int i=1; i<n; i++) {
		int x,y;
		cin>>x>>y;
		add(x,y);
		add(y,x);
	}
	dfs1(r,0);
	dfs2(r,r);
	build(1,1,n) ;
	while(m--) {
		int op,x,y,z;
		int ans=0;
		cin>>op;
		if(op==1) {
			cin>>x>>y>>z;
			while(top[x]!=top[y]) {
				if(dep[top[x]]<dep[top[y]]) {
					swap(x,y);
				}
				change(1,1,n,id[top[x]],id[x],z);
				x=fa[top[x]];
			}
			if(dep[x]>dep[y]) {
				swap(x,y);
			}
			change(1,1,n,id[x],id[y],z);
		} else if(op==2) {
			cin>>x>>y;
			while(top[x]!=top[y]) {
				if(dep[top[x]]<dep[top[y]]) {
					swap(x,y);
				}
				ans=(ans+query(1,1,n,id[top[x]],id[x]))%p;
				x=fa[top[x]];
			}
			if(dep[x]>dep[y]) {
				swap(x,y);
			}
			ans=(ans+query(1,1,n,id[x],id[y]))%p;
			cout<<ans%p<<endl;
		} else if(op==3) {
			cin>>x>>z;
			change(1,1,n,id[x],id[x]+size[x]-1,z);
		} else if(op==4) {
			cin>>x;
			cout<<query(1,1,n,id[x],id[x]+size[x]-1)%p<<endl;
		}
	}
	return 0;
}

例题 P3950 部落冲突 - 洛谷

这是一道边权转点权的树链剖分题, 只有单点修改.

  • 对于一次战争, 直接把对应的路径设为 1, 也就是更改较深的节点.
  • 对于查询, 查询路径上是否有 1, 这里用 和 或 最大值 均可.
  • 对于停战, 把路径改为 0 即可.

需要注意查询 u=v 时直接输出 Yes.

完整代码

 
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include <iostream>
using namespace std;
const int N = 3e5 + 5;
int hd[N], to[N * 2], nxt[N * 2], num = 1;
void add(int u, int v) {
    num++;
    to[num] = v;
    nxt[num] = hd[u];
    hd[u] = num;
}
int fa[N], sz[N], top[N], son[N], dfn[N], dep[N], cnt = 0;
void dfs1(int u, int f) {
    fa[u] = f;
    dep[u] = dep[f] + 1;
    sz[u] = 1;
    for (int i = hd[u]; i; i = nxt[i]) {
        int v = to[i];
        if (v == f) continue;
        dfs1(v, u);
        sz[u] += sz[v];
        if (sz[v] > sz[son[u]]) son[u] = v;
    }
}
void dfs2(int u, int ance) {
    dfn[u] = ++cnt;
    top[u] = ance;
    if (!son[u]) return;
    dfs2(son[u], ance);
    for (int i = hd[u]; i; i = nxt[i]) {
        int v = to[i];
        if (v == fa[u] || v == son[u]) continue;
        dfs2(v, v);
    }
}
int ques[N];

#define mid ((l + r) / 2)
#define lc (u * 2)
#define rc (u * 2 + 1)
int tr[N * 4];
void cg(int u, int l, int r, int x, int y) {
    if (l == r) {
        tr[u] = y;
        return;
    }
    if (x <= mid)
        cg(lc, l, mid, x, y);
    else
        cg(rc, mid + 1, r, x, y);
    tr[u] = tr[lc] + tr[rc];
}
int ask(int u, int l, int r, int x, int y) {
    if (y < l || x > r) return 0;
    if (x <= l && r <= y) {
        return tr[u];
    }

    int ans = 0;
    if (x <= mid) ans += ask(lc, l, mid, x, y);
    if (mid + 1 <= y) ans += ask(rc, mid + 1, r, x, y);
    return ans;
}
int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n - 1; i++) {
        int u, v;
        cin >> u >> v;
        add(u, v);
        add(v, u);
    }
    dfs1(1, 0);
    dfs2(1, 1);
    int wcnt = 0;
    for (int i = 1; i <= m; i++) {
        char op;
        cin >> op;
        if (op == 'Q') {
            int u, v;
            cin >> u >> v;
            if (u == v) {
                cout << "Yes\n";
                continue;
            }
            int sum = 0;
            while (top[u] != top[v]) {
                if (dep[top[u]] < dep[top[v]]) swap(u, v);
                sum += ask(1, 1, n, dfn[top[u]], dfn[u]);
                u = fa[top[u]];
            }
            if (dep[u] > dep[v]) swap(u, v);
            sum += ask(1, 1, n, dfn[son[u]], dfn[v]);
            if (sum == 0) {
                cout << "Yes\n";
            } else {
                cout << "No\n";
            }
        } else if (op == 'C') {
            int u, v;
            cin >> u >> v;
            if (dep[u] > dep[v]) swap(u, v);
            cg(1, 1, n, dfn[v], 1);
            ques[++wcnt] = v;
        } else {
            int x;
            cin >> x;
            cg(1, 1, n, dfn[ques[x]], 0);
        }
    }
    return 0;
}

例题 P2146 [NOI2015] 软件包管理器 - 洛谷

好久没有写过树链剖分的题了, 写一道练练手.

  • 对于安装操作, 答案就是从根到其的长度 - 根到其的路径上安装的数量. 然后将这条路径上所有节点改为安装状态.
  • 对于卸载操作, 答案就是其子树中已安装的软件数量, 然后将子树全部变为未安装状态.

由以上可以总结出一种维护方法: 对于已安装的节点标记为 1, 未安装的是 0. 维护路径赋值和路径总和即可.

完整代码

 
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
const int N = 1e5 + 5;
vector<int> sons[N];
int fa[N], sz[N], dep[N], son[N], top[N], dfn[N], num = 0;
void dfs1(int u) {
    dep[u] = dep[fa[u]] + 1;
    sz[u] = 1;
    for (int i : sons[u]) {
        dfs1(i);
        sz[u] += sz[i];
        if (sz[i] > sz[son[u]]) son[u] = i;
    }
}
void dfs2(int u, int ance) {
    dfn[u] = ++num;
    top[u] = ance;
    if (!son[u]) return;
    dfs2(son[u], ance);
    for (int i : sons[u]) {
        if (i == son[u]) continue;
        dfs2(i, i);
    }
}
#define lc (u * 2)
#define rc (u * 2 + 1)
#define mid ((l + r) / 2)
int tr[4 * N], lazy[4 * N];
void lz(int u, int l, int r, int x) {
    tr[u] = x * (r - l + 1);
    lazy[u] = x;
}
void pd(int u, int l, int r) {
    if (lazy[u] != -1) {
        lz(lc, l, mid, lazy[u]);
        lz(rc, mid + 1, r, lazy[u]);
        lazy[u] = -1;
    }
}
void cg(int u, int l, int r, int x, int y, int z) {
    if (x <= l && r <= y) {
        lz(u, l, r, z);
        return;
    }
    pd(u, l, r);
    if (x <= mid) cg(lc, l, mid, x, y, z);
    if (mid + 1 <= y) cg(rc, mid + 1, r, x, y, z);
    tr[u] = tr[lc] + tr[rc];
}
int ask(int u, int l, int r, int x, int y) {
    if (x <= l && r <= y) return tr[u];
    pd(u, l, r);
    int ans = 0;
    if (x <= mid) ans += ask(lc, l, mid, x, y);
    if (mid + 1 <= y) ans += ask(rc, mid + 1, r, x, y);
    return ans;
}

int qsum(int u, int v, int n) {
    int ans = 0;
    while (top[u] != top[v]) {
        if (dep[top[u]] < dep[top[v]]) swap(u, v);
        ans += ask(1, 1, n, dfn[top[u]], dfn[u]);
        u = fa[top[u]];
    }
    if (dep[u] > dep[v]) swap(u, v);
    ans += ask(1, 1, n, dfn[u], dfn[v]);
    return ans;
}
void qc(int u, int v, int n, int x) {
    while (top[u] != top[v]) {
        if (dep[top[u]] < dep[top[v]]) swap(u, v);
        cg(1, 1, n, dfn[top[u]], dfn[u], x);
        u = fa[top[u]];
    }
    if (dep[u] > dep[v]) swap(u, v);
    cg(1, 1, n, dfn[u], dfn[v], x);
}
int main() {
    int n;
    cin >> n;
    for (int i = 2; i <= n; i++) {
        cin >> fa[i];
        fa[i]++;
        sons[fa[i]].push_back(i);
    }
    dfs1(1);
    dfs2(1, 1);
    memset(lazy, -1, sizeof(lazy));
    int q;
    cin >> q;
    while (q--) {
        string s;
        int x;
        cin >> s >> x;
        x++;
        if (s == "install") {
            cout << dep[x] - qsum(1, x, n) << endl;
            qc(1, x, n, 1);
        } else {
            cout << ask(1, 1, n, dfn[x], dfn[x] + sz[x] - 1) << endl;
            cg(1, 1, n, dfn[x], dfn[x] + sz[x] - 1, 0);
        }
    }
}