/ ZYCode / 题库 /

【ZYCODE R7】删点游戏

【ZYCODE R7】删点游戏

Description

JMT有一棵树。其中 11 号节点为根节点。
定义在这颗树上删除一个点(被删除的点不为根节点)为将这个点的所有儿子节点直接连到这个点的父亲节点,并将这个点和它所相连的所有边删除。树上的每一个点有一个点权,表示删除它这一个点的代价。
定义一个节点的深度为它父亲节点的深度加 11 , 根节点的深度为 11
一共有两种操作,分别形如:
CC xx yy 表示将编号为 xx 的点的点权修改为 yy
QQ xx yy 询问将编号为 xx 的点的深度变为 yy 所需要花的删点代价和最小是多少(如果深度永远不可能变为 yy ,输出 1-1 )。**注意:每一个 QQ 操作是独立的。也就是说,在删完之后会还原。**

Format

Input

第一行有两个整数 nnqq 表示树的节点数目和询问次数。
接下来 n1n - 1 行,每行两个整数,表示树上一条边。
接下来一行有 n1n - 1 个整数,第 ii 个表示第 i+1i + 1 号节点的初始权值。
接下来 qq 行,表示询问。询问格式如题。

Output

第一行有两个整数 nnqq 表示树的节点数目和询问次数。
接下来 n1n - 1 行,每行两个整数,表示树上一条边。
接下来一行有 n1n - 1 个整数,第 ii 个表示第 i+1i + 1 号节点的初始权值。
接下来 qq 行,表示询问。询问格式如题。

Sample 1

Input

6 4
1 2
2 4
2 5
5 6
1 3
2 3 4 5 6
Q 4 2
C 2 1
Q 4 2
Q 5 4

Output

2
1
-1

Limitation

对于 15%15\% 的数据:1n103,1q1041 \leq n \leq 10^3 ,1 \leq q \leq 10^4
对于另 10%10\% 的数据:保证树为一条链
对于另 20%20\% 的数据: CC 操作次数不超过 100100
对于另 5%5\% 的数据: 树形态随机生成
对于 100%100\% 的数据:
1n1041 \leq n \leq 10^4
1点权1031 \leq 点权 \leq 10^3
1q1051 \leq q \leq 10^5

信息

ID
1056
难度
2500
分类
(无)
标签
递交数
1
已通过
0
通过率
0%
上传者