一棵树上有 n 个结点,编号分别为 1 到 n,每个结点都有一个权值 w。我们将以下面的形式来要求你对这棵树完成一些操作: CHANGE u t:把结点 u 的权值改为 t; QMAX u v:询问从点 u 到点 v 的路径上的结点的最大权值; QSUM u v: 询问从点 u 到点 v 的路径上的结点的权值和。 注意:从点 u 到点 v 的路径上的结点包括 u 和 v 本身。
输入的第一行为一个整数 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 之间。
对于每个 “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