树的统计

• 时间限制：3 秒
• 内存限制：256 MiB

题目描述

给定一棵有 $n$ 个节点的树，节点编号为 $1$ 到 $n$，每个节点都有一个整数权值。请处理以下三种操作：

• CHANGE u t：把节点 $u$ 的权值修改为 $t$；
• QMAX u v：询问节点 $u$ 到节点 $v$ 的简单路径上所有节点权值的最大值；
• QSUM u v：询问节点 $u$ 到节点 $v$ 的简单路径上所有节点权值之和。

路径包含两个端点。当 $u=v$ 时，路径只包含节点 $u$。

输入格式

第一行输入一个整数 $n$。

接下来 $n-1$ 行，每行输入两个整数 $a,b$，表示树中有一条连接节点 $a,b$ 的边。

下一行输入 $n$ 个整数 $w_1,w_2,\ldots,w_n$，其中 $w_i$ 是节点 $i$ 的初始权值。

下一行输入一个整数 $q$，表示操作数。

接下来 $q$ 行，每行输入一个操作，格式为 CHANGE u t、QMAX u v 或 QSUM u v。

输出格式

对每个 QMAX 或 QSUM 操作输出一行一个整数，表示询问结果。

样例输入 1

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

样例输出 1

4
1
2
2
10
6
5
6
5
16

数据范围

对于所有数据，$1\le n\le 3\times 10^4$，$0\le q\le 2\times 10^5$，任意时刻每个节点的权值均在 $[-3\times 10^4,3\times 10^4]$ 内。输入保证给出的图是一棵树，且操作中的节点编号合法。