题目描述

小 A 走到一个山脚下，准备给自己造一个小屋。这时候，小 A 的朋友（op，又叫管理员）打开了创造模式，然后飞到山顶放了格水。于是小 A 面前出现了一个瀑布。作为平民的小 A 只好老实巴交地爬山堵水。那么问题来了：我们把这个瀑布看成是一个 $n$ 个节点的树，每个节点有权值（爬上去的代价）。小 A 要选择一些节点，以其权值和作为代价将这些点删除（堵上），使得根节点与所有叶子结点不连通。问最小代价。不过到这还没结束。小 A 的朋友觉得这样子太便宜小 A 了，于是他还会不断地修改地形，使得某个节点的权值发生变化。不过到这还没结束。小 A 觉得朋友做得太绝了，于是放弃了分离所有叶子节点的方案。取而代之的是，每次他只要在某个子树中（和子树之外的点完全无关）。于是他找到你。

输入格式

输入文件第一行包含一个数 $n$，表示树的大小。

接下来一行包含 $n$ 个数，表示第 $i$ 个点的权值。

接下来 $n-1$ 行每行包含两个数 $fr,to$ 。表示树中有一条边 $(fr,to)$ 。

接下来一行一个整数，表示操作的个数。

接下来 $m$ 行每行表示一个操作，若该行第一个数为 $Q$，则表示询问操作，后面跟一个参数 $x$ ，表示对应子树的根；若为 $C$ ，则表示修改操作，后面接两个参数 $x,t$ ，表示将点 $x$ 的权值加上 $t$。

输出格式

对于每次询问操作，输出对应的答案，答案之间用换行隔开。

4
4 3 2 1
1 2
1 3
4 2
4
Q 1
Q 2
C 4 10
Q 1

3
1
4

提示

$1 \leq n \leq 200000,1 \leq fr,to \leq n,1 \leq x \leq n$，权值和 $t$ 均在 int 范围内且非负。

BZOJ4712