P9090 “SvR-2” G64

For two rooted binary trees $T_1, T_2$, define the result of $\operatorname{merge}(T_1,T_2)$ as a binary tree whose root’s left subtree is $T_1$ and right subtree is $T_2$. Obviously, the result of $\operatorname{merge}(T_1,T_2)$ is unique and always exists. For a rooted binary tree $T$, define a function $G_x(T)$. Here, $G_1(T)$ means: starting from the root of $T$, keep moving to the right child until reaching a node that has no right child; then set that node’s right subtree to be $T$. The resulting new tree is $G_1(T)$. For $x>1$, $G_x(T)$ satisfies: $$G_x(T)=G_1(\operatorname{merge}(G_{x-1}(T),G_{x-1}(T)))$$ Given a rooted binary tree with $n$ nodes and root $1$, let the subtree rooted at node $i$ be $T_i$. There are $q$ queries. Each query gives $x,i$. For each query, find the maximum independent set of $G_x(T_i)$.

The first line contains two integers $n,q$. Then follow $n$ lines. Each line contains two integers $ls_i,rs_i$, representing the left child and right child. If it is $0$, it means the corresponding child does not exist. Then follow $q$ lines. Each line contains two integers $x,i$, representing one query.

Output $q$ lines. Each line contains one number: the size of the maximum independent set of $G_x(T_i)$ modulo $998244353$ for this query.

### Sample Explanation For the first sample, the result of $G_2(T_5)$ is shown in the figure below (node indices are ignored):  For the second sample, I have a wonderful explanation, but unfortunately $G_{64}$ is too large to write it down here. #### Constraints and Notes **This problem enables bundled testdata and O2 optimization.** | Subtask | Constraints / Special Properties | Score | | :------: | :------: | :------: | | $1$ | $n,q,x\le 10$ | $10 \operatorname{pts}$ | | $2$ | $x =1$ | $5 \operatorname{pts}$ | | $3$ | $x\le 3$ | $10 \operatorname{pts}$ | | $4$ | $x\le 10$ | $15 \operatorname{pts}$ | | $5$ | The size of $T_i$ is guaranteed to be $1$ | $10 \operatorname{pts}$ | | $6$ | No special restrictions | $50 \operatorname{pts}$ | For $100\%$ of the testdata: $1\le x\le 10^9$, $1\le n\le 5\times 10^5$, $1\le q\le 5\times 10^5$. Translated by ChatGPT 5