409015 - 树的统计

一棵树上有 n 个结点,编号分别为 1 到 n,每个结点都有一个权值 w。我们将以下面的形式来要求你对这棵树完成一些操作: CHANGE u t:把结点 u 的权值改为 t; QMAX u v:询问从点 u 到点 v 的路径上的结点的最大权值; QSUM u v: 询问从点 u 到点 v 的路径上的结点的权值和。 注意:从点 u 到点 v 的路径上的结点包括 u 和 v 本身。

Input

输入的第一行为一个整数 n,表示结点的个数。接下来n-1行,每行2个整数a和b,表示结点 a 和结点 b 之间有一条边相连。接下来 n 行,每行一个整数,第 i 行的整数 wi 表示结点 i 的权值。接下来 1 行,为一个整数 q,表示操作的总数。 接下来 q 行,每行一个操作,以 “CHANGE u t” 或者 “QMAX u v” 或者 “QSUM u v” 的形式给出。 对于 100% 的数据,保证 1 ≤ n ≤ 30000,0 ≤ q ≤ 200000;中途操作中保证每个结点的权值 w 在 -30000 到 30000 之间。

Output

对于每个 “QMAX” 或者 “QSUM” 的操作,每行输出一个整数表示要求输出的结果。

Examples

Input

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

Output

4
1
2
2
10
6
5
6
5
16
时间限制 1 秒
内存限制 128 MB
统计
上一题 下一题