#P6913. 游戏
游戏
题目描述
小 C 和小 D 在一棵有根二叉树上玩游戏。树有 个节点,根为 。编号 到 的节点各有两个儿子,编号 到 的节点均为叶子。每片叶子给定一个权值,其余节点的初始权值为 。
一次修剪操作选取一个两个儿子都为叶子的非叶节点。操作者删除这两个儿子,并选取它们原先的一个权值作为该节点的新权值。
小 C 先手,两人交替修剪。无法再修剪时,剩余节点的权值和就是得分。小 C 希望得分最大,小 D 希望得分最小。求双方都采用最优策略时的得分。
输入格式
第一行一个整数 。
接下来 行,第 行的两个整数是节点 的两个儿子的编号。
接下来 行,第 行的整数是节点 的初始权值。
输出格式
输出一行一个整数,表示最终得分对 取模的结果。
样例
1
2 3
10
5
10
小 C 修剪节点 ,将其权值设为 ,删除节点 和 。树只剩根节点,小 D 无法操作,最终得分为 。
数据范围
,所有给出的权值均满足 。原题时间限制 1 秒,内存限制 512 MB。
| 子任务 | 分值 | 附加限制 |
|---|---|---|
| 1 | ||
| 2 | 9 | |
| 3 | 15 | 原题写满二叉树。本站该组也包含将一片叶子再分出两个儿子的树 |
| 4 | 树的深度为 (根深度为 ) | |
| 5 | 19 | |
| 6 | 20 | |
| 7 | 21 | 无 |