3033: 动态树

小W非常喜欢树，特别是动态处理树。

这天他正在玩minecraft，不小心把山上的瀑布引入了自己的家。他只好上山去堵水了。

望着眼前的瀑布，小W想到了一个动态处理树的问题：把这个山上的瀑布看做是个有n个节点的树，树从1开始编号，每个节点有一定的权值(爬上去的代价)。小W要选择一些节点，以其权值和作为代价将这些点删除(堵上)，使得根节点(山顶水源)与所有的叶子节点不连通。求最小代价。

不过还没结束，小W觉得这个问题太简单了，便加了些操作，比如，他会不断的修改地形，使得某个节点的权值发生变化。再比如，他每次询问时不一定询问的是整棵树，而是选择一棵子树进行询问。(也就是说每次将一棵子树当做询问的树，而与其他不在子树内的节点无关，这时这棵子树的根即为山顶水源)。

现在小W不会做了，你能帮助他吗？

第一行一个整数n，表示树的大小。

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

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

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

接下来m行每行代表一次操作。每行首先包含一个字符，若为字符Q，则表示询问，后面跟一个参数x表示对应子树的根；若为C，表示一次修改，后面接两个参数x, y，表示将 x的权值加上y。

对于每次询问输出一行，表示答案。

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

3
1
4