树链剖分

发表于 更新于 分类于 ， ， ， ， 阅读次数： 本文字数： 3k 阅读时长 ≈ 11 分钟

树链剖分

是一种将一棵树划分为若干条链的思想，划分后每个树上结点恰好在一条链中。

而一条链又可以转化为一段连续的区间，从而将树上问题转换为序列问题。

树链剖分的常见方式

  • 重链剖分
  • 长链剖分
  • 实链剖分

以重链剖分最常用。

重链剖分的步骤

  1. dfs 预处理树上每个点的 sizex\mathrm{size}_x；以及重儿子 sonx\mathrm{son}_x；
  2. 将根结点 root\mathrm{root} 视为轻儿子，那么每个轻儿子往下走重儿子形成的链唯一；
  3. 再次从 root\mathrm{root} 开始 dfs，并给每个结点打时间戳 dfn\mathrm{dfn}；以及反向映射 id\mathrm{id}，先递归到重儿子；
  4. dfs 过程中维护 topi\mathrm{top}_i 表示点 ii 所在的链的链头结点编号，显然对于任意轻儿子 xx，topx=x\mathrm{top}_x=x；重儿子 topx=topfax\mathrm{top}_x=\mathrm{top}_{\mathrm{fa}_x}。

重链剖分的性质

  1. 确定重儿子后，剖分形式唯一；
  2. 任意子树的 dfn\mathrm{dfn} 连续；
  3. 任意链的 dfn\mathrm{dfn} 连续；
  4. 任意一条路径，最多由 log⁡2N\log_2\mathrm{N} 条子链拼接而成；
  5. 由 44 可以推出，任意点 xx 往上切换 log⁡2N\log_2\mathrm{N} 次链到根结点出发的重链。

例题

洛谷P3379

P3379 【模板】最近公共祖先（LCA）

用树链剖分求最近公共祖先的过程：

  • 当 deptopx>deptopy\mathrm{dep}_{\mathrm{top}_x}>\mathrm{dep}_{\mathrm{top}_y}，x≔fatopxx\coloneqq \mathrm{fa}_{\mathrm{top}_x}；
  • 当 deptopx≤deptopy\mathrm{dep}_{\mathrm{top}_x}\le \mathrm{dep}_{\mathrm{top}_y}，y≔fatopyy\coloneqq \mathrm{fa}_{\mathrm{top}_y}；
  • 重复上面的步骤直到 topx=topy\mathrm{top}_x=\mathrm{top}_y。

最近公共祖先={x,depx<depyy,否则\text{最近公共祖先} = \begin{cases} x, & \mathrm{dep}_x < \mathrm{dep}_y \\ y, & \text{否则} \end{cases}

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
#include<bits/stdc++.h>
typedef int int32;
#define int long long
using namespace std;
const int N = 5e5 + 5;
int n, m, root, size[N], dep[N], fa[N], top[N], son[N], dfn[N], rdfn[N], id[N], cnt;
vector<pair<int,int>>nbr[N];
void dfs(int x, int fa)
{
	int maxi = 0;
	::size[x] = 1;
	dep[x] = dep[fa] + 1;
	::fa[x] = fa;
	for (auto& y : nbr[x])
	{
		auto& nxt = y.first, & w = y.second;
		if (nxt != fa)
		{
			dfs(nxt, x);
			::size[x] += ::size[nxt];
			if (::size[nxt] > maxi)
				son[x] = nxt, maxi = ::size[nxt];
		}
	}
	return;
}
void dfs1(int x, int fa)
{
	dfn[x] = ++cnt;
	id[cnt] = x;
	if (son[x])
	{
		top[son[x]] = top[x];
		dfs1(son[x], x);
	}
	for (auto& y : nbr[x])
	{
		auto& nxt = y.first, & w = y.second;
		if(nxt != fa && !top[nxt])
		{
			top[nxt] = nxt;
			dfs1(nxt, x);
		}
	}
	rdfn[x] = cnt;
	return;
}
int lca(int x, int y)
{
	while (top[x] != top[y])
	{
		if (dep[top[x]] > dep[top[y]])
			x = fa[top[x]];
		else
			y = fa[top[y]];
	}
	return dep[x] < dep[y] ? x : y;
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> m >> root;
	for (int i = 1; i < n; i++)
	{
		int x, y, z = 1;
		cin >> x >> y;
		nbr[x].push_back({ y,z });
		nbr[y].push_back({ x,z });
	}
	dfs(root, 0);
	top[root] = root;
	dfs1(root, 0);
	for (int i = 1; i <= m; i++)
	{
		int x, y;
		cin >> x >> y;
		cout << lca(x, y) << '\n';
	}
	return 0;
}

洛谷P3384

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
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
#include<bits/stdc++.h>
typedef int int32;
#define int long long
using namespace std;
const int N = 5e5 + 5;
int n, m, root, mod, a[N], size[N], dep[N], fa[N], top[N], son[N], dfn[N],
rdfn[N], id[N], tree[N << 2], tag[N << 2], cnt;
vector<pair<int,int>>nbr[N];
void pushup(int x)
{
	tree[x] = tree[x << 1] + tree[x << 1 | 1];
	return;
}
void addtag(int x, int l, int r, int val)
{
	tag[x] += val;
	tree[x] += (r - l + 1) * val;
	return;
}
void pushdown(int x, int l, int r)
{
	if (!tag[x])
		return;
	int mid = (l + r) >> 1;
	addtag(x << 1, l, mid, tag[x]);
	addtag(x << 1 | 1, mid + 1, r, tag[x]);
	tag[x] = 0;
	return;
}
void build(int x, int l, int r)
{
	if (l == r)
	{
		tree[x] = a[id[l]]; // 不要写成 `tree[x] = a[l]`！
		return;
	}
	int mid = (l + r) >> 1;
	build(x << 1, l, mid);
	build(x << 1 | 1, mid + 1, r);
	pushup(x);
	return;
}
void update(int x, int l, int r, int qx, int qy, int val)
{
	if (qy < l || qx > r)
		return;
	if (qx <= l && qy >= r)
	{
		addtag(x, l, r, val);
		return;
	}
	int mid = (l + r) >> 1;
	pushdown(x, l, r);
	update(x << 1, l, mid, qx, qy, val);
	update(x << 1 | 1, mid + 1, r, qx, qy, val);
	pushup(x);
	return;
}
int query(int x, int l, int r, int qx, int qy)
{
	if (qy < l || qx > r)
		return 0;
	if (qx <= l && qy >= r)
		return tree[x];
	int mid = (l + r) >> 1;
	pushdown(x, l, r);
	return query(x << 1, l, mid, qx, qy) + query(x << 1 | 1, mid + 1, r, qx, qy);
}
void dfs(int x, int fa)
{
	int maxi = 0;
	::size[x] = 1;
	dep[x] = dep[fa] + 1;
	::fa[x] = fa;
	for (auto& y : nbr[x])
	{
		auto& nxt = y.first, & w = y.second;
		if (nxt != fa)
		{
			dfs(nxt, x);
			::size[x] += ::size[nxt];
			if (::size[nxt] > maxi)
				son[x] = nxt, maxi = ::size[nxt];
		}
	}
	return;
}
void dfs1(int x, int fa)
{
	dfn[x] = ++cnt;
	id[cnt] = x;
	if (son[x])
	{
		top[son[x]] = top[x];
		dfs1(son[x], x);
	}
	for (auto& y : nbr[x])
	{
		auto& nxt = y.first, & w = y.second;
		if(nxt != fa && !top[nxt])
		{
			top[nxt] = nxt;
			dfs1(nxt, x);
		}
	}
	rdfn[x] = cnt;
	return;
}
int lca(int x, int y)
{
	while (top[x] != top[y])
	{
		if (dep[top[x]] > dep[top[y]])
			x = fa[top[x]];
		else
			y = fa[top[y]];
	}
	return dep[x] < dep[y] ? x : y;
}
void update_path(int x, int y, int val)
{
	while (top[x] != top[y])
	{
		if (dep[top[x]] > dep[top[y]])
		{
			update(1, 1, n, dfn[top[x]], dfn[x], val);
			x = fa[top[x]];
		}
		else
		{
			update(1, 1, n, dfn[top[y]], dfn[y], val);
			y = fa[top[y]];
		}
	}
	if (dep[x] > dep[y])
		swap(x,y);
	update(1, 1, n, dfn[x], dfn[y], val);
	return;
}
int query_path(int x, int y)
{
	int sum = 0;
	while (top[x] != top[y])
	{
		if (dep[top[x]] > dep[top[y]])
		{
			sum += query(1, 1, n, dfn[top[x]], dfn[x]);
			x = fa[top[x]];
		}
		else
		{
			sum += query(1, 1, n, dfn[top[y]], dfn[y]);
			y = fa[top[y]];
		}
	}
	if (dep[x] > dep[y])
		swap(x,y);
	return sum + query(1, 1, n, dfn[x], dfn[y]);
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> m >> root >> mod;
	for (int i = 1; i <= n; i++)
		cin >> a[i], a[i] %= mod;
	for (int i = 1; i < n; i++)
	{
		int x, y, z = 1;
		cin >> x >> y;
		nbr[x].push_back({ y,z });
		nbr[y].push_back({ x,z });
	}
	dfs(root, 0);
	top[root] = root;
	dfs1(root, 0);
	build(1, 1, n);
	for (int i = 1; i <= m; i++)
	{
		int opt, x, y, z;
		cin >> opt >> x;
		if (opt == 1)
		{
			cin >> y >> z;
			update_path(x, y, z % mod);
		}
		else if (opt == 2)
		{
			cin >> y;
			cout << query_path(x, y) % mod << '\n';
		}
		else if (opt == 3)
		{
			cin >> z;
			update(1, 1, n, dfn[x], rdfn[x], z % mod);
		}
		else
			cout << query(1, 1, n, dfn[x], rdfn[x]) % mod << '\n';
	}
	return 0;
}

洛谷P1505

P1505 [国家集训队] 旅游

把边权放到子结点，从而将边的问题转换成点的问题。

线段树同时维护边权和、边权最大值、边权最小值，N 操作可以直接交换边权最大值、边权最小值并取反。

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
233
234
235
236
237
238
#include<bits/stdc++.h>
typedef int int32;
#define int long long
using namespace std;
const int N = 2e5 + 5;
int n, m, root = 1, a[N], b[N], c[N], size[N], dep[N], fa[N],
top[N], son[N], dfn[N], rdfn[N], id[N], cnt;
vector<pair<int, int>>nbr[N];
struct node1 {
	bool f1, f2;
	int x;
	node1 operator+=(const node1& u) // 不要把懒标记合并直接写成覆盖！
	{
		if (u.f1)
			*this = u;
		else if (u.f2)
			if (f1)
				x = -x;
			else
				f2 = !f2;
		return *this;
	}
	bool operator!() const
	{
		return !f1 && !f2;
	}
}tag[N << 2];
struct node {
	int sum, maxi, mini, len;
	node operator+(const node& u) const
	{
		return { (sum + u.sum),max(maxi, u.maxi),
			min(mini, u.mini),len + u.len };
	}
	node operator+=(const node& u)
	{
		return *this = *this + u;
	}
	node operator+=(const node1& u)
	{
		if (u.f1)
			sum = u.x * len, maxi = u.x, mini = u.x;
		else if (u.f2)
			sum = -sum, swap(maxi, mini), maxi = -maxi, mini = -mini;
		return *this;
	}
}tree[N << 2];
void pushup(int x)
{
	tree[x] = tree[x << 1] + tree[x << 1 | 1];
	return;
}
void addtag(int x, int l, int r, node1 val)
{
	tag[x] += val;
	tree[x] += val;
	return;
}
void pushdown(int x, int l, int r)
{
	if (!tag[x])
		return;
	int mid = (l + r) >> 1;
	addtag(x << 1, l, mid, tag[x]);
	addtag(x << 1 | 1, mid + 1, r, tag[x]);
	tag[x] = { 0,0,0 };
	return;
}
void build(int x, int l, int r)
{
	if (l == r)
	{
		tree[x] = { a[id[l]],a[id[l]],a[id[l]],1 };
		return;
	}
	int mid = (l + r) >> 1;
	build(x << 1, l, mid);
	build(x << 1 | 1, mid + 1, r);
	pushup(x);
	return;
}
void update(int x, int l, int r, int qx, int qy, node1 val)
{
	if (qy < l || qx > r)
		return;
	if (qx <= l && qy >= r)
	{
		addtag(x, l, r, val);
		return;
	}
	int mid = (l + r) >> 1;
	pushdown(x, l, r);
	update(x << 1, l, mid, qx, qy, val);
	update(x << 1 | 1, mid + 1, r, qx, qy, val);
	pushup(x);
	return;
}
node query(int x, int l, int r, int qx, int qy)
{
	if (qy < l || qx > r)
		return { 0,(int)-1e9,(int)1e9,0 };
	if (qx <= l && qy >= r)
		return tree[x];
	int mid = (l + r) >> 1;
	pushdown(x, l, r);
	return query(x << 1, l, mid, qx, qy) +
		query(x << 1 | 1, mid + 1, r, qx, qy);
}
void dfs(int x, int fa)
{
	int maxi = 0;
	::size[x] = 1;
	dep[x] = dep[fa] + 1;
	::fa[x] = fa;
	for (auto& y : nbr[x])
	{
		auto& nxt = y.first, & w = y.second;
		if (nxt != fa)
		{
			a[nxt] = b[w];
			c[w] = nxt;
			dfs(nxt, x);
			::size[x] += ::size[nxt];
			if (::size[nxt] > maxi)
				son[x] = nxt, maxi = ::size[nxt];
		}
	}
	return;
}
void dfs1(int x, int fa)
{
	dfn[x] = ++cnt;
	id[cnt] = x;
	if (son[x])
	{
		top[son[x]] = top[x];
		dfs1(son[x], x);
	}
	for (auto& y : nbr[x])
	{
		auto& nxt = y.first, & w = y.second;
		if (nxt != fa && !top[nxt])
		{
			top[nxt] = nxt;
			dfs1(nxt, x);
		}
	}
	rdfn[x] = cnt;
	return;
}
int lca(int x, int y)
{
	while (top[x] != top[y])
	{
		if (dep[top[x]] > dep[top[y]])
			x = fa[top[x]];
		else
			y = fa[top[y]];
	}
	return dep[x] < dep[y] ? x : y;
}
void update_path(int x, int y, node1 val)
{
	while (top[x] != top[y])
	{
		if (dep[top[x]] > dep[top[y]])
		{
			update(1, 1, n, dfn[top[x]], dfn[x], val);
			x = fa[top[x]];
		}
		else
		{
			update(1, 1, n, dfn[top[y]], dfn[y], val);
			y = fa[top[y]];
		}
	}
	if (dep[x] > dep[y])
		swap(x, y);
	update(1, 1, n, dfn[x] + 1, dfn[y], val);
	return;
}
node query_path(int x, int y)
{
	node sum = { 0,(int)-1e9,(int)1e9,0 };
	while (top[x] != top[y])
	{
		if (dep[top[x]] > dep[top[y]])
		{
			sum += query(1, 1, n, dfn[top[x]], dfn[x]);
			x = fa[top[x]];
		}
		else
		{
			sum += query(1, 1, n, dfn[top[y]], dfn[y]);
			y = fa[top[y]];
		}
	}
	if (dep[x] > dep[y])
		swap(x, y);
	return sum + query(1, 1, n, dfn[x] + 1, dfn[y]);
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n;
	for (int i = 1; i < n; i++)
	{
		int x, y, z = i;
		cin >> x >> y >> b[i];
		x++;
		y++;
		nbr[x].push_back({ y,z });
		nbr[y].push_back({ x,z });
	}
	dfs(root, 0);
	top[root] = root;
	dfs1(root, 0);
	build(1, 1, n);
	cin >> m;
	for (int i = 1; i <= m; i++)
	{
		string opt;
		int x, y;
		cin >> opt >> x >> y;
		if (opt == "C")
			update(1, 1, n, dfn[c[x]], dfn[c[x]], { true,false,y });
		else if (opt == "N")
			update_path(++x, ++y, { false,true,0 });
		else if (opt == "SUM")
			cout << query_path(++x, ++y).sum << '\n';
		else if (opt == "MAX")
			cout << query_path(++x, ++y).maxi << '\n';
		else if (opt == "MIN")
			cout << query_path(++x, ++y).mini << '\n';
	}
	return 0;
}

洛谷P2590

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
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
#include<bits/stdc++.h>
typedef int int32;
#define int long long
using namespace std;
const int N = 2e5 + 5;
int n, m, root = 1, a[N], size[N], dep[N], fa[N],
top[N], son[N], dfn[N], rdfn[N], id[N], cnt;
vector<pair<int, int>>nbr[N];
struct node1 {
	bool f1;
	int x;
	node1 operator+=(const node1& u)
	{
		return *this = u;
	}
	bool operator!() const
	{
		return !f1;
	}
}tag[N << 2];
struct node {
	int sum, maxi, len;
	node operator+(const node& u) const
	{
		return { (sum + u.sum),max(maxi, u.maxi),len + u.len };
	}
	node operator+=(const node& u)
	{
		return *this = *this + u;
	}
	node operator+=(const node1& u)
	{
		if (u.f1)
			sum = u.x * len, maxi = u.x;
		return *this;
	}
}tree[N << 2];
void pushup(int x)
{
	tree[x] = tree[x << 1] + tree[x << 1 | 1];
	return;
}
void addtag(int x, int l, int r, node1 val)
{
	tag[x] += val;
	tree[x] += val;
	return;
}
void pushdown(int x, int l, int r)
{
	if (!tag[x])
		return;
	int mid = (l + r) >> 1;
	addtag(x << 1, l, mid, tag[x]);
	addtag(x << 1 | 1, mid + 1, r, tag[x]);
	tag[x] = { 0,0 };
	return;
}
void build(int x, int l, int r)
{
	if (l == r)
	{
		tree[x] = { a[id[l]],a[id[l]],1 };
		return;
	}
	int mid = (l + r) >> 1;
	build(x << 1, l, mid);
	build(x << 1 | 1, mid + 1, r);
	pushup(x);
	return;
}
void update(int x, int l, int r, int qx, int qy, node1 val)
{
	if (qy < l || qx > r)
		return;
	if (qx <= l && qy >= r)
	{
		addtag(x, l, r, val);
		return;
	}
	int mid = (l + r) >> 1;
	pushdown(x, l, r);
	update(x << 1, l, mid, qx, qy, val);
	update(x << 1 | 1, mid + 1, r, qx, qy, val);
	pushup(x);
	return;
}
node query(int x, int l, int r, int qx, int qy)
{
	if (qy < l || qx > r)
		return { 0,(int)-1e9,0 };
	if (qx <= l && qy >= r)
		return tree[x];
	int mid = (l + r) >> 1;
	pushdown(x, l, r);
	return query(x << 1, l, mid, qx, qy) +
		query(x << 1 | 1, mid + 1, r, qx, qy);
}
void dfs(int x, int fa)
{
	int maxi = 0;
	::size[x] = 1;
	dep[x] = dep[fa] + 1;
	::fa[x] = fa;
	for (auto& y : nbr[x])
	{
		auto& nxt = y.first, & w = y.second;
		if (nxt != fa)
		{
			dfs(nxt, x);
			::size[x] += ::size[nxt];
			if (::size[nxt] > maxi)
				son[x] = nxt, maxi = ::size[nxt];
		}
	}
	return;
}
void dfs1(int x, int fa)
{
	dfn[x] = ++cnt;
	id[cnt] = x;
	if (son[x])
	{
		top[son[x]] = top[x];
		dfs1(son[x], x);
	}
	for (auto& y : nbr[x])
	{
		auto& nxt = y.first, & w = y.second;
		if (nxt != fa && !top[nxt])
		{
			top[nxt] = nxt;
			dfs1(nxt, x);
		}
	}
	rdfn[x] = cnt;
	return;
}
int lca(int x, int y)
{
	while (top[x] != top[y])
	{
		if (dep[top[x]] > dep[top[y]])
			x = fa[top[x]];
		else
			y = fa[top[y]];
	}
	return dep[x] < dep[y] ? x : y;
}
void update_path(int x, int y, node1 val)
{
	while (top[x] != top[y])
	{
		if (dep[top[x]] > dep[top[y]])
		{
			update(1, 1, n, dfn[top[x]], dfn[x], val);
			x = fa[top[x]];
		}
		else
		{
			update(1, 1, n, dfn[top[y]], dfn[y], val);
			y = fa[top[y]];
		}
	}
	if (dep[x] > dep[y])
		swap(x, y);
	update(1, 1, n, dfn[x], dfn[y], val);
	return;
}
node query_path(int x, int y)
{
	node sum = { 0,(int)-1e9,0 };
	while (top[x] != top[y])
	{
		if (dep[top[x]] > dep[top[y]])
		{
			sum += query(1, 1, n, dfn[top[x]], dfn[x]);
			x = fa[top[x]];
		}
		else
		{
			sum += query(1, 1, n, dfn[top[y]], dfn[y]);
			y = fa[top[y]];
		}
	}
	if (dep[x] > dep[y])
		swap(x, y);
	return sum + query(1, 1, n, dfn[x], dfn[y]);
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n;
	for (int i = 1; i < n; i++)
	{
		int x, y, z = i;
		cin >> x >> y;
		nbr[x].push_back({ y,z });
		nbr[y].push_back({ x,z });
	}
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	dfs(root, 0);
	top[root] = root;
	dfs1(root, 0);
	build(1, 1, n);
	cin >> m;
	for (int i = 1; i <= m; i++)
	{
		string opt;
		int x, y;
		cin >> opt >> x >> y;
		if (opt == "CHANGE")
			update(1, 1, n, dfn[x], dfn[x], { true,y });
		else if (opt == "QMAX")
			cout << query_path(x, y).maxi << '\n';
		else if (opt == "QSUM")
			cout << query_path(x, y).sum << '\n';
	}
	return 0;
}