一棵树上有 个节点，编号分别为 到 ，每个节点都有一个权值 。我们将以下面的形式来要求你对这棵树完成一些操作：
CHANGE u t
QMAX u v
QSUM u v
注意：从点 到点 的路径上的节点包括 和 本身。
输入的第一行为一个整数 ，表示节点的个数。接下来 行，每行 个整数 和 ，表示节点 和节点 之间有一条边相连。
接下来 行，每行一个整数，第 行的整数 表示节点 的权值。
接下来 行，为一个整数 ，表示操作的总数。
接下来 行，每行一个操作，以 CHANGE u t 或者 QMAX u v 或者 QSUM u v 的形式给出。
对于每个 QMAX 或者 QSUM 的操作，每行输出一个整数表示要求输出的结果。
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
对于 的数据，，。
中途操作中保证每个节点的权值 在 到 之间。
