【ZYCODE R7】删点游戏
Description
JMT有一棵树。其中 号节点为根节点。
定义在这颗树上删除一个点(被删除的点不为根节点)为将这个点的所有儿子节点直接连到这个点的父亲节点,并将这个点和它所相连的所有边删除。树上的每一个点有一个点权,表示删除它这一个点的代价。
定义一个节点的深度为它父亲节点的深度加 , 根节点的深度为 。
一共有两种操作,分别形如:
表示将编号为 的点的点权修改为 。
询问将编号为 的点的深度变为 所需要花的删点代价和最小是多少(如果深度永远不可能变为 ,输出 )。**注意:每一个 操作是独立的。也就是说,在删完之后会还原。**
Format
Input
第一行有两个整数 , 表示树的节点数目和询问次数。
接下来 行,每行两个整数,表示树上一条边。
接下来一行有 个整数,第 个表示第 号节点的初始权值。
接下来 行,表示询问。询问格式如题。
Output
第一行有两个整数 , 表示树的节点数目和询问次数。
接下来 行,每行两个整数,表示树上一条边。
接下来一行有 个整数,第 个表示第 号节点的初始权值。
接下来 行,表示询问。询问格式如题。
Sample 1
Input
Output
Limitation
对于 的数据:
对于另 的数据:保证树为一条链
对于另 的数据: 操作次数不超过
对于另 的数据: 树形态随机生成
对于 的数据:
信息
- ID
- 1056
- 难度
- 2500
- 分类
- (无)
- 标签
- 递交数
- 1
- 已通过
- 0
- 通过率
- 0%
- 上传者