bzoj#P4712. 洪水
洪水
题目描述
小 A 走到一个山脚下,准备给自己造一个小屋。这时候,小 A 的朋友(OP,又叫管理员)打开了创造模式,然后飞到山顶放了格水。于是小 A 面前出现了一个瀑布。作为平民的小 A 只好老实巴交地爬山堵水。那么问题来了:我们把这个瀑布看成是一个 个节点的树,每个节点有权值(爬上去的代价)。小 A 要选择一些节点,以其权值和作为代价将这些点删除(堵上),使得根节点与所有叶子结点不连通。问最小代价。不过到这还没结束。小 A 的朋友觉得这样子太便宜小 A 了,于是他还会不断地修改地形,使得某个节点的权值发生变化。不过到这还没结束。小 A 觉得朋友做得太绝了,于是放弃了分离所有叶子节点的方案。取而代之的是,每次他只要在某个子树中(和子树之外的点完全无关)。于是他找到你。
输入格式
输入文件第一行包含一个数 ,表示树的大小。
接下来一行包含 个数,表示第 个点的权值。
接下来 行每行包含两个数 。表示书中有一条边 。
接下来一行一个整数,表示操作的个数。
接下来 行每行表示一个操作,若该行第一个数为 Q
,则表示询问操作,后面跟一个参数 ,表示对应子树的根;若为 C
,则表示修改操作,后面接两个参数 ,表示将点 的权值加上 。
,保证任意 都为非负数。
输出格式
对于每次询问操作,输出对应的答案,答案之间用换行隔开。
4
4 3 2 1
1 2
1 3
4 2
4
Q 1
Q 2
C 4 10
Q 1
3
1
4