P5281 [ZJOI2019] Minimax Search.

Jiutiao Keliansi is a girl who likes playing games. To improve her gaming skills, she wants to arm herself with theory. This problem is related to the famous Minimax search. Keliansi has a rooted tree with the root numbered $1$. Define the depth of the root as $1$, and the depth of any other node as its parent’s depth plus $1$. Given the values on the leaf nodes, Keliansi defines the value of each non-leaf node as follows: - For a non-leaf node at odd depth, its value is the maximum among the values of all its children. - For a non-leaf node at even depth, its value is the minimum among the values of all its children. At the beginning, Keliansi sets the value of the leaf node numbered $i$ to be $i$, and computes the root’s value as $W$. Now, the evil Cedyks wants to change the root’s value by modifying the values of some leaf nodes. Cedyks has designed a quantum attacker. After it is activated, Cedyks will randomly gain control of a non-empty set of leaf nodes $S$, and can spend some energy to modify the values of the leaf nodes in $S$. However, modifying leaf node values costs energy. For a leaf node $i \in S$, its initial value is $i$. Suppose Cedyks changes its value to $w_i$ ($w_i$ **can be any integer, including negative numbers**). Then the energy needed for this attack is $\max_{i\in S} |i − w_i|$. Cedyks wants to save as much energy as possible, so he will always **complete the attack with the minimum energy**, i.e. under the minimum energy cost, make the root’s value change. Let $w(S)$ be the energy Cedyks will spend after gaining control of set $S$. In particular, for some sets $S$, no matter how the values of the leaf nodes in $S$ are changed, the root’s value will not change. In this case, $w(S)$ is defined as $n$. For convenience, we call $w(S)$ the stability of $S$. When there are $m$ leaf nodes, there are $2^m − 1$ different non-empty sets of leaf nodes. Before launching the attack, Cedyks wants to estimate the energy he may need. So he gives an interval $[L, R]$, and wants to know, for each $k \in [L, R]$, how many sets $S$ satisfy $w(S) = k$.

The first line contains three integers $n, L, R(n ≥ 2,1 \leq L \leq R \leq n)$. The next $n - 1$ lines each contain two integers $u, v$, indicating an edge in the tree.

Output one line with $R-L+1$ integers. The $i$-th integer indicates how many sets $S$ have $w(S) = L+i-1$. The answer may be very large; output it modulo $998244353$.

#### Explanation of Sample 1 At the beginning, under Keliansi’s setting (the value of leaf node $i$ is $i$), the root’s value is $4$. There are $3$ leaf nodes $\{2,3,4\}$ in the tree, and there are $7$ non-empty sets of leaf nodes, among which: - $\{4\}, \{2,4\}, \{3,4\}, \{2,3,4\}$ have stability $1$. As long as you slightly modify the value of leaf node $4$, the root’s value will change. - $\{2\}, \{3\}$ have stability $5$, because the value at node $5$ is the smaller one between $2$ and $3$. If you only modify node $2$ or only modify node $3$, the value at node $5$ is always less than or equal to $3$, so the root’s value is always $4$. - $\{2,3\}$ has stability $3$. To make the root’s value change, the value at node $5$ must be greater than $4$, so both $w_2$ and $w_3$ must be greater than $4$. Therefore the stability is $3$. One feasible plan is to set both $w_2$ and $w_3$ to $5$. #### Constraints | Test Point | $n$ | Other Constraints | Test Point | $n$ | Other Constraints | | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | | $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$ | None | | $4$ | $\le5\times 10^3$ | $L=R=n$ | $9$ | $\le2\times 10^5$ | None | | $5$ | $\le5\times 10^3$ | $L=R=n$ | $10$ | $\le2\times 10^5$ | None | For all testdata, it is guaranteed that $n\ge2$, $1\le L \le R \le n$. Translated by ChatGPT 5