#P6913. 游戏

    ID: 6744 传统题 1000ms 512MiB 尝试: 2 已通过: 1 难度: 10 上传者: 标签>CF3000省选/NOI-树形 DP奇偶性分析阈值二值化零和博弈

游戏

题目描述

小 C 和小 D 在一棵有根二叉树上玩游戏。树有 2n+12n+1 个节点,根为 11。编号 11 到 nn 的节点各有两个儿子,编号 n+1n+1 到 2n+12n+1 的节点均为叶子。每片叶子给定一个权值,其余节点的初始权值为 00。

一次修剪操作选取一个两个儿子都为叶子的非叶节点。操作者删除这两个儿子,并选取它们原先的一个权值作为该节点的新权值。

小 C 先手,两人交替修剪。无法再修剪时,剩余节点的权值和就是得分。小 C 希望得分最大,小 D 希望得分最小。求双方都采用最优策略时的得分。

输入格式

第一行一个整数 nn。

接下来 nn 行,第 ii 行的两个整数是节点 ii 的两个儿子的编号。

接下来 n+1n+1 行,第 ii 行的整数是节点 n+in+i 的初始权值。

输出格式

输出一行一个整数,表示最终得分对 998244353998244353 取模的结果。

样例

1
2 3
10
5
10

小 C 修剪节点 11,将其权值设为 1010,删除节点 22 和 33。树只剩根节点,小 D 无法操作,最终得分为 1010。

数据范围

1≤n≤1061\le n\le10^6,所有给出的权值均满足 0≤w<9982443530\le w<998244353。原题时间限制 1 秒,内存限制 512 MB。

子任务 分值 附加限制
1 n=1n=1
2 9 n≤10n\le10
3 15 原题写满二叉树。本站该组也包含将一片叶子再分出两个儿子的树
4 树的深度为 n+1n+1(根深度为 11)
5 19 n≤103n\le10^3
6 20 n≤105n\le10^5
7 21 无

原 PDF 题面