[ZJOI2019] Minimax搜索

题目描述

九条可怜是一个喜欢玩游戏的女孩子。为了增强自己的游戏水平,她想要用理论的武器武装自己。这道题和著名的 Minimax 搜索有关。 可怜有一棵有根树,根节点编号为 $1$。定义根节点的深度为 $1$,其他节点的深度为它的父亲的深度加一。同时在叶子节点权值给定的情况下,可怜用如下方式定义了每一个非节点的权值: - 对于深度为奇数的非叶子节点,它的权值是它所有子节点的权值最大值。 - 对于深度为偶数的非叶子节点,它的权值是它所有子节点的权值最小值。 最开始,可怜令编号为 $i$ 的叶子节点权值为 i,并计算得到了根节点的权值为 $W$。 现在,邪恶的 Cedyks 想要通过修改某些叶子节点的权值,来让根节点的权值发生改变。Cedyks 设计了一个量子攻击器,在攻击器发动后,Cedyks 会随机获得一个非空的叶子节点集合 $S$ 的控制权,并可以花费一定的能量来修改 $S$ 中的叶子节点的权值。 然而,修改叶子节点的权值也要消耗能量,对于 $S$ 中的叶子节点 $i$,它的初始权值为 $i$,假设 Cedyks 把它的权值修改成了 $w_i$($w_i$ **可以是任意整数,包括负数**),则 Cedyks 在这次攻击中,需要花费的能量为 $\max_{i\in S} |i − w_i|$。 Cedyks 想要尽可能节约能量,于是他总是会**以最少的能量来完成攻击**,即在花费的能量最小的情况下,让根节点的权值发生改变。令 $w(S)$ 为 Cedyks 在获得了集合 $S$ 的控制权后,会花费的能量。特殊地,对于某些集合 $S$,可能无论如何改变 $S$ 中叶子节点的权值,根节点的权值都不会发生改变,这时,$w(S)$ 的值被定义为 $n$。为了方便,我们称 $w(S)$ 为 $S$ 的稳定度。 当有 $m$ 个叶子节点的时候,一共有 $2^m − 1$ 种不同的叶子节点的非空集合。在发动攻击前,Cedyks 想要先预估一下自己需要花费的能量。于是他给出了一个区间 $[L, R]$,他想要知道对于每一个 $k \in [L, R]$,有多少个集合 $S$ 满足 $w(S) = k$。

输入输出格式

输入格式


第一行输入三个整数 $n,L,R(n ≥ 2,1 \leq L \leq R \leq n)$。 接下来 $n - 1$ 行每行两个整数 $u,v$,表示树上的一条边。

输出格式


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

输入输出样例

输入样例 #1

5 1 5
1 5
1 4
5 3
5 2

输出样例 #1

4 0 1 0 2

说明

#### 样例 1 解释 最开始,在可怜的设定下($i$ 号叶子节点的权值为 $i$),根节点的权值为 $4$。 树上一共有 $3$ 个叶子节点 $\{2,3,4\}$,一共有 $7$ 个非空的叶子节点权值,其中: - $\{4\}, \{2,4\}, \{3,4\}, \{2,3,4\}$ 的稳定度为 $1$,只要稍微修改 $4$ 号叶子节点的权值,根节点的权值就会发生改变。 - $\{2\},\{3\}$ 的稳定度为 $5$,因为 $5$ 号的权值是 $2,3$ 的较小值,在只修改 $2$ 号或者 $3$ 号的情况下,$5$ 号点的权值始终小于等于 $3$,所以根节点的权值始终为 $4$。 - $\{2,3\}$ 的稳定度为 $3$,要让根节点的权值发生改变,必须让 $5$ 的权值大于 $4$,因此 $w_2 ,w_3$都必须要大于 $4$,所以稳定度为 $3$,一个可行的方案是把 $w_2 ,w_3$ 都设为 $5$。 #### 数据规模与约定 | 测试点 | $n$ | 其他约定 | 测试点 | $n$ | 其他约定 | | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | | $1$ | $\le10$ | $L=R=n$ | $6$ | $\le2\times 10^5$ | $R-L\le50$ | | $2$ | $\le50$ | $L=R=n$ | $7$ | $\le2\times 10^5$ | $R-L\le50$ | | $3$ | $\le50$ | $L=R=n$ | $8$ | $\le2\times 10^5$ | 无 | | $4$ | $\le5\times 10^3$ | $L=R=n$ | $9$ | $\le2\times 10^5$ | 无 | | $5$ | $\le5\times 10^3$ | $L=R=n$ | $10$ | $\le2\times 10^5$ | 无 | 对于 $100\%$ 的数据,保证 $n\ge2$,$1\le L \le R \le n$。