#2523. 树的统计

树的统计

Description

一棵树有nn 个节点,编号为1n1~n ,每个节点都有一个权值ww

完成以下操作:

CHANGECHANGE uu tt ,把节点uu 的权值修改为tt

QMAXQMAX uu vv ,询问从节点uu 到节点vv 路径上节点的最大权值;

QSUMQSUM uu vv ,询问从节点uu 到节点vv 路径上节点的权值和(注意:从节点uu 到节点vv 路径上的节点包括uuvv 自身)。

Format

Input

11行包含一个整数nn ,表示节点的个数。

接下来的n1n -1行,每行都包含两个整数aabb ,表示在节点aa和节点bb 之间有一条边相连。

接下来的nn行,第ii 行的整数wiw_i 表示节点ii 的权值。

接下来的一行包含一个整数qq ,表示操作的总数。

最后有qq 行,每行都表示一种操作,操作形式如上所述。

其中,1n300001≤n ≤300000q2000000≤q ≤200000,保证操作中每个节点的权值ww 都为3000030000-30000~30000

Output

对每个QMAXQMAX或者QSUMQSUM的操作,都单行输出一个整数表示要求的结果。

Samples

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

来源

HYSBZ1036