题目描述
原题来自：ZJOI 2008
一树上有
n
n 个节点，编号分别为
1
1 到
n
n，每个节点都有一个权值
w
w。我们将以下面的形式来要求你对这棵树完成一些操作：
CHANGE u t ：把节点
u
u 权值改为
t
t；
QMAX u v ：询问点
u
u 到点
v
v 路径上的节点的最大权值；
QSUM u v ：询问点
u
u 到点
v
v 路径上的节点的权值和。
注意：从点
u
u 到点
v
v 路径上的节点包括
u
u 和
v
v 本身。
输入
第一行为一个数
n
n，表示节点个数；
接下来
n-1
n−1 行，每行两个整数
a,b
a,b，表示节点
a
a 与节点
b
b 之间有一条边相连；
接下来
n
n 行，每行一个整数，第
i
i 行的整数
w_i
w
i
表示节点
i
i 的权值；
接下来一行，为一个整数
q
q ，表示操作总数；
接下来
q
q 行，每行一个操作，以 CHANGE u t 或 QMAX u v 或 QSUM u v的形式给出。
输出
对于每个 QMAX 或 QSUM 的操作，每行输出一个整数表示要求的结果。
样例输入
4
1 2
2 3
4 1
4 2 1 3
12
QMAX 3 4
QMAX 3 3
QMAX 3 2
QMAX 2 3
QSUM 3 4
QSUM 2 1
CHANGE 1 5
QMAX 3 4
CHANGE 3 6
QMAX 3 4
QMAX 2 4
QSUM 3 4
样例输出
4
1
2
2
10
6
5
6
5
16
提示
数据范围与提示
对于
100\%
100% 的数据，有
1\le n \le 3\times 10^4, 0 \le q \le 2\times 10^5
1≤n≤3×104,0≤q≤2×105。中途操作中保证每个节点的权值
w
w 在
-30000
−30000 至
30000
30000 之间。
来源/分类
ybttg 树链剖分