#P5281. [ZJOI2019] Minimax搜索

[ZJOI2019] Minimax搜索

题目描述

九条可怜是一个喜欢玩游戏的女孩子。为了增强自己的游戏水平,她想要用理论的武器武装自己。这道题和著名的 Minimax 搜索有关。

可怜有一棵有根树,根节点编号为 11。定义根节点的深度为 11,其他节点的深度为它的父亲的深度加一。同时在叶子节点权值给定的情况下,可怜用如下方式定义了每一个非节点的权值:

  • 对于深度为奇数的非叶子节点,它的权值是它所有子节点的权值最大值。
  • 对于深度为偶数的非叶子节点,它的权值是它所有子节点的权值最小值。

最开始,可怜令编号为 ii 的叶子节点权值为 i,并计算得到了根节点的权值为 WW

现在,邪恶的 Cedyks 想要通过修改某些叶子节点的权值,来让根节点的权值发生改变。Cedyks 设计了一个量子攻击器,在攻击器发动后,Cedyks 会随机获得一个非空的叶子节点集合 SS 的控制权,并可以花费一定的能量来修改 SS 中的叶子节点的权值。

然而,修改叶子节点的权值也要消耗能量,对于 SS 中的叶子节点 ii,它的初始权值为 ii,假设 Cedyks 把它的权值修改成了 wiw_iwiw_i 可以是任意整数,包括负数),则 Cedyks 在这次攻击中,需要花费的能量为 maxiSiwi\max_{i\in S} |i − w_i|

Cedyks 想要尽可能节约能量,于是他总是会以最少的能量来完成攻击,即在花费的能量最小的情况下,让根节点的权值发生改变。令 w(S)w(S) 为 Cedyks 在获得了集合 SS 的控制权后,会花费的能量。特殊地,对于某些集合 SS,可能无论如何改变 SS 中叶子节点的权值,根节点的权值都不会发生改变,这时,w(S)w(S) 的值被定义为 nn。为了方便,我们称 w(S)w(S)SS 的稳定度。

当有 mm 个叶子节点的时候,一共有 2m12^m − 1 种不同的叶子节点的非空集合。在发动攻击前,Cedyks 想要先预估一下自己需要花费的能量。于是他给出了一个区间 [L,R][L, R],他想要知道对于每一个 k[L,R]k \in [L, R],有多少个集合 SS 满足 w(S)=kw(S) = k

输入格式

第一行输入三个整数 n,L,R(n2,1LRn)n,L,R(n ≥ 2,1 \leq L \leq R \leq n)

接下来 n1n - 1 行每行两个整数 u,vu,v,表示树上的一条边。

输出格式

输出一行 RL+1R-L+1 个整数,第 ii 个整数表示 w(S)w(S)L+i1L+i-1 的集合 SS 有多少个。答案可能会很大,请对 998244353998244353 取模后输出。

5 1 5
1 5
1 4
5 3
5 2
4 0 1 0 2

提示

样例 1 解释

最开始,在可怜的设定下(ii 号叶子节点的权值为 ii),根节点的权值为 44

树上一共有 33 个叶子节点 {2,3,4}\{2,3,4\},一共有 77 个非空的叶子节点权值,其中:

  • {4},{2,4},{3,4},{2,3,4}\{4\}, \{2,4\}, \{3,4\}, \{2,3,4\} 的稳定度为 11,只要稍微修改 44 号叶子节点的权值,根节点的权值就会发生改变。
  • {2},{3}\{2\},\{3\} 的稳定度为 55,因为 55 号的权值是 2,32,3 的较小值,在只修改 22 号或者 33 号的情况下,55 号点的权值始终小于等于 33,所以根节点的权值始终为 44
  • {2,3}\{2,3\} 的稳定度为 33,要让根节点的权值发生改变,必须让 55 的权值大于 44,因此 w2,w3w_2 ,w_3都必须要大于 44,所以稳定度为 33,一个可行的方案是把 w2,w3w_2 ,w_3 都设为 55

数据规模与约定

测试点 nn 其他约定 测试点 nn 其他约定
11 10\le10 L=R=nL=R=n 66 2×105\le2\times 10^5 RL50R-L\le50
22 50\le50 77
33 88
44 5×103\le5\times 10^3 99
55 1010

对于 100%100\% 的数据,保证 n2n\ge21LRn1\le L \le R \le n