fsy's blog

燃峥嵘岁月，烈日终破云。

重链剖分做题小记

发表于 更新于
本文字数： 26k 阅读时长 ≈ 24 分钟

重链剖分，可以将树上的任意一条路径划分成不超过 $\mathcal{O}(\log n)$ 条连续的链，每条链上的点深度互不相同（即是自底向上的一条链，链上所有点的 LCA 为链的一个端点）。——OI wiki

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
144
145
146
147
148
149
#include <bits/stdc++.h>
#define LL long long
#define ULL unsigned long long
#define LD long double
#define reg register
#define _rep(i, x, y) for(int i = x; i <= y; i++)
#define _per(i, x, y) for(int i = x; i >= y; i--)
template <typename T>
inline void read(T &x) {
	x = 0; T f = (T) 1;
	char c = getchar();
	for(; !isdigit(c); c = getchar()) {if(c == '-') f = -f;}
	for(; isdigit(c); c = getchar()) x = x * 10 + c - 48;
	x *= f;
}
template <typename T, typename... Args>
inline void read(T& x, Args&... args) {
    read(x); read(args...); 
}
template <typename T>
inline void write(T x) {
	if(x < 0) {x = -x; putchar('-');}
	if(x > 9) write(x / 10);
	putchar(x % 10 + '0');
}
template <typename T>
inline void writesp(T x, char sp = ' ') {write(x); putchar(sp);}
const int maxN = 1e5 + 10, maxM = 1e5 + 10;
// initialization
int w[maxN];
int n, m, r, P;
struct Edge {
    int from, to, nxt;
} edge[maxM << 1];
int head[maxN], sz = 0;
void add_edge(int u, int v) {
    edge[++sz].from = u; edge[sz].to = v; edge[sz].nxt = head[u]; head[u] = sz;
}
// hld dfs part
int dep[maxN], siz[maxN], fa[maxN], hson[maxN];
int dfn[maxN], tp[maxN], rank[maxN], wrank[maxN], timer = 0;
void dfs1(int u, int f, int d) {
    dep[u] = d; siz[u] = 1; hson[u] = 0; fa[u] = f;
    int max_size = -1;
    for(int i = head[u]; i; i = edge[i].nxt) {
        int v = edge[i].to;
        if(v == f) continue;
        dfs1(v, u, d + 1); 
        siz[u] += siz[v];
        if(siz[v] > max_size) hson[u] = v, max_size = siz[v];
    }
}
void dfs2(int u, int top) {
    dfn[u] = ++timer; tp[u] = top; rank[timer] = u; wrank[timer] = w[u];
    if(!hson[u]) return;
    dfs2(hson[u], top);
    for(int i = head[u]; i; i = edge[i].nxt) {
        int v = edge[i].to;
        if(v == fa[u] || v == hson[u]) continue;
        dfs2(v, v);
    }
}
// segment tree part
struct node {int val, tag;};
struct SegmentTree {
    node tree[maxN << 2];
    void push_up(int o) {tree[o].val = tree[o << 1].val + tree[o << 1 | 1].val;}
    void push_down(int o, int l, int r) {
        if(tree[o].tag) {
            int mid = (l + r) >> 1; 
            tree[o << 1].val = (tree[o << 1].val + 1ll * tree[o].tag * (mid - l + 1) % P) % P;
            tree[o << 1 | 1].val = (tree[o << 1 | 1].val + 1ll * tree[o].tag * (r - mid) % P) % P;
            tree[o << 1].tag = (tree[o << 1].tag + tree[o].tag) % P;
            tree[o << 1 | 1].tag = (tree[o << 1 | 1].tag + tree[o].tag) % P;
            tree[o].tag = 0;
        }
    }
    void build(int o, int l, int r) {
        if(l == r) {tree[o].val = wrank[l] % P; return;}
        int mid = (l + r) >> 1;
        build(o << 1, l, mid); build(o << 1 | 1, mid + 1, r); push_up(o); return;
    }
    void modify(int o, int l, int r, int lx, int rx, int delta) {
        if(r < lx || rx < l) return;
        if(lx <= l && r <= rx) {
            tree[o].val = (tree[o].val + 1ll * delta * (r - l + 1) % P) % P;
            tree[o].tag = (tree[o].tag + delta) % P; return;
        }
        push_down(o, l, r);
        int mid = (l + r) >> 1;
        modify(o << 1, l, mid, lx, rx, delta); modify(o << 1 | 1, mid + 1, r, lx, rx, delta); push_up(o); return;
    }
    int query(int o, int l, int r, int lx, int rx) {
        if(r < lx || rx < l) return 0;
        if(lx <= l && r <= rx) return tree[o].val;
        push_down(o, l, r);
        int mid = (l + r) >> 1;
        return (query(o << 1, l, mid, lx, rx) + query(o << 1 | 1, mid + 1, r, lx, rx)) % P;
    }
} sgt;
// hld query part
struct HLD {
    void subtree_upd(int u, int k) {sgt.modify(1, 1, n, dfn[u], dfn[u] + siz[u] - 1, k);}
    int subtree_query(int u) {return sgt.query(1, 1, n, dfn[u], dfn[u] + siz[u] - 1);}
    void path_upd(int u, int v, int k) {
        while(tp[u] != tp[v]) {
            if(dep[tp[u]] < dep[tp[v]]) std::swap(u, v);
            sgt.modify(1, 1, n, dfn[tp[u]], dfn[u], k);
            u = fa[tp[u]];
        }
        if(dep[u] > dep[v]) std::swap(u, v);
        sgt.modify(1, 1, n, dfn[u], dfn[v], k);
    }
    int path_query(int u, int v) {
        int ans = 0;
        while(tp[u] != tp[v]) {
            if(dep[tp[u]] < dep[tp[v]]) std::swap(u, v);
            ans = (ans + sgt.query(1, 1, n, dfn[tp[u]], dfn[u])) % P;
            u = fa[tp[u]];
        }
        if(dep[u] > dep[v]) std::swap(u, v);
        return (ans + sgt.query(1, 1, n, dfn[u], dfn[v])) % P;
    }
} hld;
int main() {
//	freopen(".in", "r", stdin);
//	freopen(".out", "w", stdout);
    read(n, m, r, P);
    _rep(i, 1, n) read(w[i]);
    _rep(i, 1, n - 1) {
        int u, v; read(u, v);
        add_edge(u, v); add_edge(v, u);
    }
    dfs1(r, 0, 0); dfs2(r, r);
    sgt.build(1, 1, n);
    _rep(i, 1, m) {
        int opt, a, b, c; read(opt, a);
        if(opt == 1) {
            read(b, c); hld.path_upd(a, b, c);
        } else if(opt == 2) {
            read(b); writesp(hld.path_query(a, b), '\n');
        } else if(opt == 3) {
            read(b); hld.subtree_upd(a, b);
        } else {
            writesp(hld.subtree_query(a), '\n');
        }
    }
	return 0;
}

P3313 [SDOI2014]旅行

比较裸的树剖。对每一个宗教开一个动态开点线段树 / 离散化+线段树即可。

代码用的是动态开点线段树。

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
#include <bits/stdc++.h>
#define LL long long
#define ULL unsigned long long
#define LD long double
#define reg register
#define _rep(i, x, y) for(int i = x; i <= y; i++)
#define _per(i, x, y) for(int i = x; i >= y; i--)
template <typename T>
inline void read(T &x) {
	x = 0; T f = (T) 1;
	char c = getchar();
	for(; !isdigit(c); c = getchar()) {if(c == '-') f = -f;}
	for(; isdigit(c); c = getchar()) x = x * 10 + c - 48;
	x *= f;
}
template <typename T, typename... Args>
inline void read(T& x, Args&... args) {
    read(x); read(args...);
}
template <typename T>
inline void write(T x) {
	if(x < 0) {x = -x; putchar('-');}
	if(x > 9) write(x / 10);
	putchar(x % 10 + '0');
}
template <typename T>
inline void writesp(T x, char sp = ' ') {write(x); putchar(sp);}
const int maxN = 1e5 + 10;
int n, q;
int w[maxN], c[maxN];
struct Edge {int from, to, nxt;} edge[maxN << 1];
int head[maxN], sz = 0;
void add_edge(int u, int v) {
	edge[++sz].from = u; edge[sz].to = v; edge[sz].nxt = head[u]; head[u] = sz;
}
int siz[maxN], hson[maxN], dep[maxN], fa[maxN];
void dfs1(int u, int f, int d) {
	fa[u] = f; dep[u] = d; siz[u] = 1;
	int max_size = -1;
	for(int i = head[u]; i; i = edge[i].nxt) {
		if(edge[i].to == f) continue;
		dfs1(edge[i].to, u, d + 1);
		siz[u] += siz[edge[i].to];
		if(siz[edge[i].to] > max_size) max_size = siz[edge[i].to], hson[u] = edge[i].to;
	}
}
int dfn[maxN], rk[maxN], wrank[maxN], tp[maxN], timer = 0;
void dfs2(int u, int top) {
	dfn[u] = ++timer; rk[timer] = u; wrank[timer] = w[u]; tp[u] = top;
	if(!hson[u]) return;
	dfs2(hson[u], top);
	for(int i = head[u]; i; i = edge[i].nxt) {
		if(edge[i].to == fa[u] || edge[i].to == hson[u]) continue;
		dfs2(edge[i].to, edge[i].to);
	}
}
int roots[maxN], qwq = 0;
struct node {int lc, rc, max, sum;} tree[maxN * 40];
void push_up(int o) {
	tree[o].sum = tree[tree[o].lc].sum + tree[tree[o].rc].sum;
	tree[o].max = std::max(tree[tree[o].lc].max, tree[tree[o].rc].max);
}
void destroy(int o) {tree[o].sum = tree[o].max = 0;}
void modify(int &o, int l, int r, int pos, int delta) { // WJP AK IOI
	if(!o) {o = ++qwq;}
	if(l == r) {tree[o].max = tree[o].sum = delta; return;}
	int mid = (l + r) >> 1;
	if(pos <= mid) modify(tree[o].lc, l, mid, pos, delta);
	else modify(tree[o].rc, mid + 1, r, pos, delta);
	push_up(o);
}
void erase(int &o, int l, int r, int pos) {
	if(!o) return;
	if(l == r) {destroy(o); return;}
	int mid = (l + r) >> 1;
	if(pos <= mid) erase(tree[o].lc, l, mid, pos);
	else erase(tree[o].rc, mid + 1, r, pos);
	push_up(o);
//	if(!tree[o].lc && !tree[o].rc) destroy(o);
}
int query_max(int &o, int l, int r, int lx, int rx) {
	if(!o) return 0;
	if(rx < l || r < lx) return 0;
	if(lx <= l && r <= rx) return tree[o].max;
	int mid = (l + r) >> 1;
	return std::max(query_max(tree[o].lc, l, mid, lx, rx), query_max(tree[o].rc, mid + 1, r, lx, rx));
}
int query_sum(int &o, int l, int r, int lx, int rx) {
	if(!o) return 0;
	if(rx < l || r < lx) return 0;
	if(lx <= l && r <= rx) return tree[o].sum;
	int mid = (l + r) >> 1;
	return (query_sum(tree[o].lc, l, mid, lx, rx) + query_sum(tree[o].rc, mid + 1, r, lx, rx));
}

int main() {
	read(n, q);
	_rep(i, 1, n) read(w[i], c[i]);
	_rep(i, 1, n - 1) {
		int x, y; read(x, y);
		add_edge(x, y); add_edge(y, x);
	}
	dfs1(1, 0, 0); dfs2(1, 1);
	_rep(i, 1, n) modify(roots[c[rk[i]]], 1, n, i, w[rk[i]]);
	_rep(i, 1, q) {
		char s[3]; int x, y;
		scanf("%s", s); read(x, y);
		if(s[1] == 'C') {
			erase(roots[c[x]], 1, n, dfn[x]);
			c[x] = y; modify(roots[c[x]], 1, n, dfn[x], w[x]);
		} else if(s[1] == 'W') {
			erase(roots[c[x]], 1, n, dfn[x]);
			w[x] = y;
			modify(roots[c[x]], 1, n, dfn[x], y);
		} else if(s[1] == 'S') {
			int ans = 0, k = c[x];
			while(tp[x] != tp[y]) {
				if(dep[tp[x]] < dep[tp[y]]) std::swap(x, y);
				ans += query_sum(roots[k], 1, n, dfn[tp[x]], dfn[x]);
				x = fa[tp[x]];
			}
			if(dep[x] > dep[y]) std::swap(x, y);
			ans += query_sum(roots[k], 1, n, dfn[x], dfn[y]);
			writesp(ans, '\n');
		} else if(s[1] == 'M') {
			int ans = 0, k = c[x];
			while(tp[x] != tp[y]) {
				if(dep[tp[x]] < dep[tp[y]]) std::swap(x, y);
				ans = std::max(ans, query_max(roots[k], 1, n, dfn[tp[x]], dfn[x]));
				x = fa[tp[x]];
			}
			if(dep[x] > dep[y]) std::swap(x, y);
			ans = std::max(ans, query_max(roots[k], 1, n, dfn[x], dfn[y]));
			writesp(ans, '\n');
		}
	}
	return 0;
}

P1505 [国家集训队]旅游

本题是关于边权的，但是经典的重链剖分都是修改，查询点权，应该如何转化？

很明显，我们可以将边权转移到其深度较深的点，在查询的时候去掉 LCA 的贡献即可。

操作略多，写起来很烦….

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
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
#include <bits/stdc++.h>
#define LL long long
#define ULL unsigned long long
#define LD long double
#define reg register
#define _rep(i, x, y) for(int i = x; i <= y; i++)
#define _per(i, x, y) for(int i = x; i >= y; i--)
template <typename T>
inline void read(T &x) {
	x = 0; T f = (T) 1;
	char c = getchar();
	for(; !isdigit(c); c = getchar()) {if(c == '-') f = -f;}
	for(; isdigit(c); c = getchar()) x = x * 10 + c - 48;
	x *= f;
}
template <typename T, typename... Args>
inline void read(T& x, Args&... args) {
    read(x); read(args...);
}
template <typename T>
inline void write(T x) {
	if(x < 0) {x = -x; putchar('-');}
	if(x > 9) write(x / 10);
	putchar(x % 10 + '0');
}
template <typename T>
inline void writesp(T x, char sp = ' ') {write(x); putchar(sp);}
const int maxN = 2e5 + 10, maxM = 2e5 + 10, inf = -2e9 - 9, maxinf = 2e9 + 9;
int n, m, ll[maxM], rr[maxM], leaf[maxN];
char opt[5];
struct Edge {int from, to, nxt, val;} edge[maxM << 1];
int head[maxN], w[maxN], sz = 0;
void add_edge(int u, int v, int w) {edge[++sz].from = u; edge[sz].to = v; edge[sz].val = w; edge[sz].nxt = head[u]; head[u] = sz;}
int siz[maxN], fa[maxN], hson[maxN], dep[maxN];
void dfs1(int u, int f, int d, int E) {
	fa[u] = f; dep[u] = d; siz[u] = 1; hson[u] = 0; w[u] = edge[E].val;
	int max_size = -1;
	for(int i = head[u]; i; i = edge[i].nxt) {
		if(edge[i].to == f) continue;
		dfs1(edge[i].to, u, d + 1, i);
		siz[u] += siz[edge[i].to];
		if(max_size < siz[edge[i].to]) {
			hson[u] = edge[i].to; max_size = siz[edge[i].to];
		}
	}
}
int timer = 0, dfn[maxN], tp[maxN], rank[maxN];
void dfs2(int u, int top) {
	dfn[u] = ++timer; rank[timer] = u; tp[u] = top;
	if(!hson[u]) return;
	dfs2(hson[u], top);
	for(int i = head[u]; i; i = edge[i].nxt) {
		if(edge[i].to == hson[u] || edge[i].to == fa[u]) continue;
		dfs2(edge[i].to, edge[i].to);
	} 
}
struct node {
	int min, max, sum, tag, neg;
};
struct SegmentTree {
	node tree[maxN << 2];
	void push_up(int o) {
		tree[o].sum = tree[o << 1].sum + tree[o << 1 | 1].sum;
		tree[o].min = std::min(tree[o << 1].min, tree[o << 1 | 1].min);
		tree[o].max = std::max(tree[o << 1].max, tree[o << 1 | 1].max);
	}
	void push_down(int o, int l, int r) {
		if(tree[o].tag) {
			int mid = (l + r) >> 1;
			tree[o << 1].sum = tree[o << 1].sum + 1ll * (mid - l + 1) * tree[o].tag;
			tree[o << 1 | 1].sum = tree[o << 1 | 1].sum + 1ll * (r - mid) * tree[o].tag;
			tree[o << 1].min = tree[o << 1].min + tree[o].tag;
			tree[o << 1 | 1].min = tree[o << 1 | 1].min + tree[o].tag;
			tree[o << 1].max = tree[o << 1].max + tree[o].tag;
			tree[o << 1 | 1].max = tree[o << 1 | 1].max + tree[o].tag;
			tree[o << 1].tag = tree[o << 1].tag + tree[o].tag;
			tree[o << 1 | 1].tag = tree[o << 1 | 1].tag + tree[o].tag;
			tree[o].tag = 0;
		}
	}
	void push_downneg(int o, int l, int r) {
		if(tree[o].neg == 1) {
			int mid = (l + r) >> 1;
			tree[o << 1].neg ^= 1; tree[o << 1 | 1].neg ^= 1;
			tree[o << 1].sum *= -1; tree[o << 1 | 1].sum *= -1;
			int lmax = tree[o << 1].max, lmin = tree[o << 1].min, rmax = tree[o << 1 | 1].max, rmin = tree[o << 1 | 1].min;
			tree[o << 1].max = -lmin, tree[o << 1].min = -lmax, tree[o << 1 | 1].max = -rmin, tree[o << 1 | 1].min = -rmax;
			tree[o].neg = 0;
		}
	}
	void build(int o, int l, int r) {
		if(l == r) {tree[o].min = tree[o].max = tree[o].sum = w[rank[l]]; tree[o].neg = 0; leaf[l] = o; return;}
		int mid = (l + r) >> 1;
		build(o << 1, l, mid);
		build(o << 1 | 1, mid + 1, r);
		push_up(o);
	} 
	void modify(int o, int l, int r, int x, int k) {
		if(r < x || x < l) return;
		if(l == x && r == x) {
			tree[o].sum = k;
			tree[o].min = k;
			tree[o].max = k;
			return;
		}
		push_downneg(o, l, r);
		int mid = (l + r) >> 1;
		modify(o << 1, l, mid, x, k);
		modify(o << 1 | 1, mid + 1, r, x, k);
		push_up(o);
	}
	void negative(int o, int l, int r, int xl, int xr) {
		if(r < xl || xr < l) return;
		if(xl <= l && r <= xr) {
			int minval = tree[o].min, maxval = tree[o].max;
			tree[o].sum = -tree[o].sum; tree[o].max = -minval; tree[o].min = -maxval; tree[o].neg ^= 1; 
			return;
		}
		push_downneg(o, l, r);
		int mid = (l + r) >> 1;
		negative(o << 1, l, mid, xl, xr);
		negative(o << 1 | 1, mid + 1, r, xl, xr);
		push_up(o);
	}
	int querysum(int o, int l, int r, int xl, int xr) {
		if(r < xl || xr < l) return 0;
		if(xl <= l && r <= xr) return tree[o].sum;
		push_downneg(o, l, r);
		int mid = (l + r) >> 1;
		return querysum(o << 1, l, mid, xl, xr) + querysum(o << 1 | 1, mid + 1, r, xl, xr);
	}
	int querymax(int o, int l, int r, int xl, int xr) {
		if(r < xl || xr < l) return inf;
		if(xl <= l && r <= xr) return tree[o].max;
		push_downneg(o, l, r);
		int mid = (l + r) >> 1;
		return std::max(querymax(o << 1, l, mid, xl, xr), querymax(o << 1 | 1, mid + 1, r, xl, xr));
	}
	int querymin(int o, int l, int r, int xl, int xr) {
		if(r < xl || xr < l) return maxinf;
		if(xl <= l && r <= xr) return tree[o].min;
		push_downneg(o, l, r);
		int mid = (l + r) >> 1;
		return std::min(querymin(o << 1, l, mid, xl, xr), querymin(o << 1 | 1, mid + 1, r, xl, xr));
	}
	void debug(int o, int l, int r) {
		printf("Node #%d, Range: [%d, %d], Status: [Sum = %d, Min = %d, Max = %d, Tag = %d, Neg = %d]\n", o, l, r, tree[o].sum, tree[o].min, tree[o].max, tree[o].tag, tree[o].neg);
		if(l == r) return;
		debug(o << 1, l, (l + r) >> 1); debug(o << 1 | 1, ((l + r) >> 1) + 1, r);
	}
} sgt;
struct heavylight {
	void range_negative(int u, int v) {
		while(tp[u] != tp[v]) {
			if(dep[tp[u]] < dep[tp[v]]) std::swap(u, v);	
			
			sgt.negative(1, 1, n, dfn[tp[u]], dfn[u]);
			u = fa[tp[u]];
		}
		if(u > v) std::swap(u, v);
		if(u != v) sgt.negative(1, 1, n, dfn[u] + 1, dfn[v]);
	}
	int path_sum(int u, int v) {
		int ans = 0;
		while(tp[u] != tp[v]) {
			if(dep[tp[u]] < dep[tp[v]]) std::swap(u, v);
			ans += sgt.querysum(1, 1, n, dfn[tp[u]], dfn[u]);
			u = fa[tp[u]];
		}
//		std::cout << u << " " << v << " " << tp[u] << " " << dfn[u] << " " << dfn[tp[u]] << " " << ans << std::endl; 	
		if(u > v) std::swap(u, v);
		if(u != v) ans += sgt.querysum(1, 1, n, dfn[u] + 1, dfn[v]);
		return ans;
	}
	int path_max(int u, int v) {
		int ans = inf;
		while(tp[u] != tp[v]) {
			if(dep[tp[u]] < dep[tp[v]]) std::swap(u, v);
			ans = std::max(ans, sgt.querymax(1, 1, n, dfn[tp[u]], dfn[u]));
			u = fa[tp[u]];
		}
		if(u > v) std::swap(u, v);
		if(u != v) ans = std::max(ans, sgt.querymax(1, 1, n, dfn[u] + 1, dfn[v]));
		return ans;
	}
	int path_min(int u, int v) {
		int ans = maxinf;
		while(tp[u] != tp[v]) {
			if(dep[tp[u]] < dep[tp[v]]) std::swap(u, v);
			ans = std::min(ans, sgt.querymin(1, 1, n, dfn[tp[u]], dfn[u]));
			u = fa[tp[u]];
		}
		if(u > v) std::swap(u, v);
		if(u != v) ans = std::min(ans, sgt.querymin(1, 1, n, dfn[u] + 1, dfn[v]));
		return ans;	
	}
} hld;
int main() {
	read(n);
	_rep(i, 1, n - 1) {
		int u, v, w; read(u, v, w); u++; v++; ll[i] = u; rr[i] = v;
		add_edge(u, v, w); add_edge(v, u, w);
	}
	dfs1(1, 0, 0, 0); dfs2(1, 1); 
//	_rep(i, 1, n) {
//		std::cout << w[i] << std::endl;
//	}
	sgt.build(1, 1, n);
	read(m);
	_rep(i, 1, m) {
		scanf("%s", opt); int x, y; read(x, y); 
//		std::cout << opt[0] << " " << opt[1] << " " << opt[2] << std::endl;
		if(opt[0] == 'C') {
			int q = (dep[ll[x]] > dep[rr[x]] ? ll[x] : rr[x]);
//			std::cout << q << std::endl;
			sgt.modify(1, 1, n, dfn[q], y);
		} else if(opt[0] == 'N') {
			x++; y++;
			hld.range_negative(x, y);
		} else if(opt[1] == 'U') {
			x++; y++;
			writesp(hld.path_sum(x, y), '\n');
		} else if(opt[1] == 'I') {
			x++; y++;
			writesp(hld.path_min(x, y), '\n');
		} else {
			x++; y++;
			writesp(hld.path_max(x, y), '\n');
		}
	}
	return 0;
}

P4315 月下”毛景树”

转边权的方法上文已经说过，这里不再赘述。

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
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
#include <bits/stdc++.h>
#define LL long long
#define ULL unsigned long long
#define LD long double
#define reg register
#define _rep(i, x, y) for(int i = x; i <= y; i++)
#define _per(i, x, y) for(int i = x; i >= y; i--)
template <typename T>
inline void read(T &x) {
	x = 0; T f = (T) 1;
	char c = getchar();
	for(; !isdigit(c); c = getchar()) {if(c == '-') f = -f;}
	for(; isdigit(c); c = getchar()) x = x * 10 + c - 48;
	x *= f;
}
template <typename T, typename... Args>
inline void read(T& x, Args&... args) {
    read(x); read(args...);
}
template <typename T>
inline void write(T x) {
	if(x < 0) {x = -x; putchar('-');}
	if(x > 9) write(x / 10);
	putchar(x % 10 + '0');
}
template <typename T>
inline void writesp(T x, char sp = ' ') {write(x); putchar(sp);}
const int maxN = 1e5 + 10;
int n, ll[maxN], rr[maxN], w[maxN], head[maxN], sz = 0;
char opt[5];
struct Edge {
	int from, to, nxt, val;
} edge[maxN << 1];
void add_edge(int u, int v, int w) {
	edge[++sz].from = u; edge[sz].to = v; edge[sz].val = w; edge[sz].nxt = head[u]; head[u] = sz;
}
int dep[maxN], fa[maxN], siz[maxN], hson[maxN];
void dfs1(int u, int f, int d, int E) {
	dep[u] = d; fa[u] = f; siz[u] = 1; hson[u] = 0; w[u] = edge[E].val;
	int max_size = -1;
	for(int i = head[u]; i; i = edge[i].nxt) {
		if(edge[i].to == f) continue;
		dfs1(edge[i].to, u, d + 1, i);
		siz[u] += siz[edge[i].to];
		if(siz[edge[i].to] > max_size) max_size = siz[edge[i].to], hson[u] = edge[i].to;
	}
}
int timer = 0, dfn[maxN], tp[maxN], rank[maxN];
void dfs2(int u, int top) {
	dfn[u] = ++timer; rank[timer] = u; tp[u] = top;
	if(!hson[u]) return;
	dfs2(hson[u], top);
	for(int i = head[u]; i; i = edge[i].nxt) {
		if(edge[i].to == fa[u] || edge[i].to == hson[u]) continue;
		dfs2(edge[i].to, edge[i].to);
	}
}
struct node {
	int max, tag, cover;
};
struct SegmentTree {
	node tree[maxN << 2];
	void push_up(int o) {tree[o].max = std::max(tree[o << 1].max, tree[o << 1 | 1].max);}
	void push_down(int o, int l, int r) {
		if(tree[o].cover != -1) {
			tree[o << 1].cover = tree[o << 1 | 1].cover = tree[o].cover;
			tree[o << 1].max = tree[o << 1 | 1].max = tree[o].cover;
			tree[o << 1].tag = tree[o << 1 | 1].tag = 0;
			tree[o].cover = -1;
		}
		if(tree[o].tag) {
			tree[o << 1].max += tree[o].tag; tree[o << 1 | 1].max += tree[o].tag;
			tree[o << 1].tag += tree[o].tag; tree[o << 1 | 1].tag += tree[o].tag;
			tree[o].tag = 0;
		}
	}
	void build(int o, int l, int r) {
		tree[o].cover = -1;
		if(l == r) {tree[o].max = w[rank[l]]; tree[o].tag = 0; return;}
		int mid = (l + r) >> 1;
		build(o << 1, l, mid);
		build(o << 1 | 1, mid + 1, r);
		push_up(o);
	}
	void modify_set(int o, int l, int r, int xl, int xr, int val) {
		if(r < xl || xr < l) return;
		if(xl <= l && r <= xr) {
			tree[o].cover = tree[o].max = val;
			tree[o].tag = 0; return;
		}
		push_down(o, l, r);
		int mid = (l + r) >> 1;
		modify_set(o << 1, l, mid, xl, xr, val);
		modify_set(o << 1 | 1, mid + 1, r, xl, xr, val);
		push_up(o);
	}
	void modify_add(int o, int l, int r, int xl, int xr, int delta) {
		if(r < xl || xr < l) return;
		if(xl <= l && r <= xr) {
			tree[o].max += delta; tree[o].tag += delta;
			return;
		}
		push_down(o, l, r);
		int mid = (l + r) >> 1;
		modify_add(o << 1, l, mid, xl, xr, delta);
		modify_add(o << 1 | 1, mid + 1, r, xl, xr, delta);
		push_up(o);
	}
	int querymax(int o, int l, int r, int xl, int xr) {
		if(r < xl || xr < l) return -1e9;
		if(xl <= l && r <= xr) return tree[o].max;
		push_down(o, l, r);
		int mid = (l + r) >> 1;
		return std::max(querymax(o << 1, l, mid, xl, xr), querymax(o << 1 | 1, mid + 1, r, xl, xr));
	}
	void debug(int o, int l, int r) {
		printf("Node #%d, Range: [%d, %d], Status: [Max = %d, AddTag = %d, Cover = %d]\n", o, l, r, tree[o].max, tree[o].tag, tree[o].cover);
		if(l == r) return;
		int mid = (l + r) >> 1;
		debug(o << 1, l, mid); debug(o << 1 | 1, mid + 1, r);
	}
} sgt;
struct HLD {
	void path_set(int u, int v, int val) {
		while(tp[u] != tp[v]) {
			if(dep[tp[u]] < dep[tp[v]]) std::swap(u, v);
			sgt.modify_set(1, 1, n, dfn[tp[u]], dfn[u], val);
			u = fa[tp[u]];
		}
		if(dep[u] > dep[v]) std::swap(u, v);
		if(u != v) sgt.modify_set(1, 1, n, dfn[u] + 1, dfn[v], val);
	}
	void path_add(int u, int v, int delta) {
		while(tp[u] != tp[v]) {
			if(dep[tp[u]] < dep[tp[v]]) std::swap(u, v);
			sgt.modify_add(1, 1, n, dfn[tp[u]], dfn[u], delta);
			u = fa[tp[u]];
		}
		if(dep[u] > dep[v]) std::swap(u, v);
		if(u != v) sgt.modify_add(1, 1, n, dfn[u] + 1, dfn[v], delta);
	}
	int path_querymax(int u, int v) {
		int ans = -1e9;
		while(tp[u] != tp[v]) {
			if(dep[tp[u]] < dep[tp[v]]) std::swap(u, v);
			ans = std::max(ans, sgt.querymax(1, 1, n, dfn[tp[u]], dfn[u]));
			u = fa[tp[u]];
		}
		if(dep[u] > dep[v]) std::swap(u, v);
		if(u != v) ans = std::max(ans, sgt.querymax(1, 1, n, dfn[u] + 1, dfn[v]));
		return ans;
	}
} hld;
int main() {
	read(n);
	_rep(i, 1, n - 1) {
		int u, v, w; read(u, v, w);
		ll[i] = u; rr[i] = v;
		add_edge(u, v, w); add_edge(v, u, w);
	}
	dfs1(1, 0, 0, 0); dfs2(1, 1); sgt.build(1, 1, n);
	while(1) {
		int x, y, z;
		std::cin >> opt;
		if(opt[0] == 'S') {
			return 0;
		} else if(opt[1] == 'h') {
			read(x, y);
			int q = (dep[ll[x]] > dep[rr[x]] ? ll[x] : rr[x]);
			sgt.modify_set(1, 1, n, dfn[q], dfn[q], y);
		} else if(opt[1] == 'o') {
			read(x, y, z);
			hld.path_set(x, y, z);
		} else if(opt[1] == 'd') {
			read(x, y, z);
			hld.path_add(x, y, z);
		} else {
			read(x, y);
			writesp(hld.path_querymax(x, y), '\n');
		}
	}
	return 0;
}

P3258 [JLOI2014]松鼠的新家

这是一道树上差分题目，也可以用树剖做。

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
#include <bits/stdc++.h>
#define LL long long
#define ULL unsigned long long
#define LD long double
#define reg register
#define _rep(i, x, y) for(int i = x; i <= y; i++)
#define _per(i, x, y) for(int i = x; i >= y; i--)
template <typename T>
inline void read(T &x) {
	x = 0; T f = (T) 1;
	char c = getchar();
	for(; !isdigit(c); c = getchar()) {if(c == '-') f = -f;}
	for(; isdigit(c); c = getchar()) x = x * 10 + c - 48;
	x *= f;
}
template <typename T, typename... Args>
inline void read(T& x, Args&... args) {
    read(x); read(args...);
}
template <typename T>
inline void write(T x) {
	if(x < 0) {x = -x; putchar('-');}
	if(x > 9) write(x / 10);
	putchar(x % 10 + '0');
}
template <typename T>
inline void writesp(T x, char sp = ' ') {write(x); putchar(sp);}
const int maxN = 3e5 + 10;
int n, a[maxN];
struct Edge {
	int from, to, nxt;
} edge[maxN << 1];
int head[maxN], sz = 0;
void add_edge(int u, int v) {
	edge[++sz].from = u; edge[sz].to = v; edge[sz].nxt = head[u]; head[u] = sz;
}
int dep[maxN], fa[maxN], siz[maxN], hson[maxN];
void dfs1(int u, int f, int d) {
	dep[u] = d; fa[u] = f; siz[u] = 1; hson[u] = 0;
	int max_size = -1;
	for(int i = head[u]; i; i = edge[i].nxt) {
		if(edge[i].to == fa[u]) continue;
		dfs1(edge[i].to, u, d + 1);
		siz[u] += siz[edge[i].to];
		if(siz[edge[i].to] > max_size) max_size = siz[edge[i].to], hson[u] = edge[i].to;
	}
}
int timer = 0, dfn[maxN], tp[maxN], rank[maxN];
void dfs2(int u, int top) {
	tp[u] = top; dfn[u] = ++timer; rank[timer] = u;
	if(!hson[u]) return;
	dfs2(hson[u], top);
	for(int i = head[u]; i; i = edge[i].nxt) {
		int v = edge[i].to;
		if(v == fa[u] || v == hson[u]) continue;
		dfs2(v, v);
	}
}
struct node {
	int sum, tag;
};
struct SegmentTree {
	node tree[maxN << 2];
	void push_up(int o) {tree[o].sum = tree[o << 1].sum + tree[o << 1 | 1].sum;}
	void push_down(int o, int l, int r) {
		if(tree[o].tag) {
			int mid = (l + r) >> 1;
			tree[o << 1].sum += tree[o].tag * (mid - l + 1);
			tree[o << 1 | 1].sum += tree[o].tag * (r - mid);
			tree[o << 1].tag += tree[o].tag;
			tree[o << 1 | 1].tag += tree[o].tag;
			tree[o].tag = 0;
		}
	}
	void build(int o, int l, int r) {
		if(l == r) {tree[o].sum = 0; return;}
		int mid = (l + r) >> 1;
		build(o << 1, l, mid);
		build(o << 1 | 1, mid + 1, r);
		push_up(o);
	}
	void modify(int o, int l, int r, int xl, int xr, int k = 1) {
		if(r < xl || xr < l) return;
		if(xl <= l && r <= xr) {
			tree[o].sum += (r - l + 1) * k;
			tree[o].tag += k; return;
		}
		push_down(o, l, r);
		int mid = (l + r) >> 1;
		modify(o << 1, l, mid, xl, xr, k);
		modify(o << 1 | 1, mid + 1, r, xl, xr, k);
		push_up(o);
	}
	int query(int o, int l, int r, int xl, int xr) {
		if(r < xl || xr < l) return 0;
		if(xl <= l && r <= xr) {
			return tree[o].sum;
		}
		push_down(o, l, r);
		int mid = (l + r) >> 1;
		return query(o << 1, l, mid, xl, xr) + query(o << 1 | 1, mid + 1, r, xl, xr);
	}
} sgt;
struct HLD {
	void visit(int u, int v, int flg = 1) {
		int st = u, en = v;
		while(tp[u] != tp[v]) {
			if(dep[tp[u]] < dep[tp[v]]) std::swap(u, v);
			sgt.modify(1, 1, n, dfn[tp[u]], dfn[u]);
			u = fa[tp[u]];
		}
		if(dep[u] > dep[v]) std::swap(u, v);
		sgt.modify(1, 1, n, dfn[u], dfn[v]);
		if(flg) sgt.modify(1, 1, n, dfn[st], dfn[st], -1);
	}
} hld;
int main() {
	read(n);
	_rep(i, 1, n) read(a[i]);
	_rep(i, 1, n - 1) {
		int u, v; read(u, v);
		add_edge(u, v); add_edge(v, u);
	}
	dfs1(1, 0, 0); dfs2(1, 1); sgt.build(1, 1, n);
	_rep(i, 1, n - 1) {
		hld.visit(a[i], a[i + 1], (i != 1));
	}
	_rep(i, 1, n) {
		writesp(sgt.query(1, 1, n, dfn[i], dfn[i]) - (i == a[n]), '\n');
	}
	return 0;
}