Control of Randomness
Contest: Codeforces Round 992 (Div. 2)
Difficulty rating: 2100
Tags: combinatorics, dfs and similar, dp, graphs, greedy, math, probabilities, trees

You are given a tree with $$$n$$$ vertices.

Let's place a robot in some vertex $$$v \ne 1$$$, and suppose we initially have $$$p$$$ coins. Consider the following process, where in the $$$i$$$-th step (starting from $$$i = 1$$$):

- If $$$i$$$ is odd, the robot moves to an adjacent vertex in the direction of vertex $$$1$$$;
- Else, $$$i$$$ is even. You can either pay one coin (if there are some left) and then the robot moves to an adjacent vertex in the direction of vertex $$$1$$$, or not pay, and then the robot moves to an adjacent vertex chosen uniformly at random.

The process stops as soon as the robot reaches vertex $$$1$$$. Let $$$f(v, p)$$$ be the minimum possible expected number of steps in the process above if we spend our coins optimally.

Answer $$$q$$$ queries, in the $$$i$$$-th of which you have to find the value of $$$f(v_i, p_i)$$$, modulo$$$^{\text{∗}}$$$ $$$998\,244\,353$$$.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^3$$$). The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$q$$$ ($$$2 \le n \le 2 \cdot 10^3$$$; $$$1 \le q \le 2 \cdot 10^3$$$) — the number of vertices in the tree and the number of queries.

The next $$$n - 1$$$ lines contain the edges of the tree, one edge per line. The $$$i$$$-th line contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$; $$$u_i \neq v_i$$$), denoting the edge between the nodes $$$u_i$$$ and $$$v_i$$$.

The next $$$q$$$ lines contain two integers $$$v_i$$$ and $$$p_i$$$ ($$$2 \le v_i \le n$$$; $$$0 \le p_i \le n$$$).

It's guaranteed that the given edges form a tree.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10 ^ 3$$$.

It is guaranteed that the sum of $$$q$$$ over all test cases does not exceed $$$2 \cdot 10 ^ 3$$$.

Output format:
For each test case, print $$$q$$$ integers: the values of $$$f(v_i, p_i)$$$ modulo $$$998\,244\,353$$$.

Formally, let $$$M = 998\,244\,353$$$. It can be shown that the answer can be expressed as an irreducible fraction $$$\frac{p}{q}$$$, where $$$p$$$ and $$$q$$$ are integers and $$$q \not \equiv 0 \pmod{M}$$$. Output the integer equal to $$$p \cdot q^{-1} \bmod M$$$. In other words, output such an integer $$$x$$$ that $$$0 \le x < M$$$ and $$$x \cdot q \equiv p \pmod{M}$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
The tree in the first test case:

In the first query, the expected value is equal to $$$1$$$, since the robot starts moving from vertex $$$2$$$ to vertex $$$1$$$ in the first step and the process stops.

Let's calculate the expected value in the second query ($$$x$$$ is the number of steps):

- $$$P(x < 2) = 0$$$, the distance to vertex $$$1$$$ is $$$2$$$ and the robot cannot reach it in fewer steps.
- $$$P(x = 2) = \frac{1}{3}$$$, since there is only one sequence of steps leading to $$$x = 2$$$. This is $$$3 \rightarrow_{1} 2 \rightarrow_{0.33} 1$$$ with probability $$$1 \cdot \frac{1}{3}$$$.
- $$$P(x \bmod 2 = 1) = 0$$$, since the robot can reach vertex $$$1$$$ by only taking an even number of steps.
- $$$P(x = 4) = \frac{2}{9}$$$: possible paths $$$3 \rightarrow_{1} 2 \rightarrow_{0.67} [3, 4] \rightarrow_{1} 2 \rightarrow_{0.33} 1$$$.
- $$$P(x = 6) = \frac{4}{27}$$$: possible paths $$$3 \rightarrow_{1} 2 \rightarrow_{0.67} [3, 4] \rightarrow_{1} 2 \rightarrow_{0.67} [3, 4] \rightarrow_{1} 2 \rightarrow_{0.33} 1$$$.
- $$$P(x = i \cdot 2) = \frac{2^{i - 1}}{3^i}$$$ in the general case.

As a result, $$$f(v, p) = \sum\limits_{i=1}^{\infty}{i \cdot 2 \cdot \frac{2^{i - 1}}{3^i}} = 6$$$.

The tree in the second test case:

Example input:
2
4 4
1 2
2 3
2 4
2 0
3 0
4 0
3 1
12 10
1 2
2 3
2 4
1 5
5 6
6 7
6 8
6 9
8 10
10 11
10 12
6 0
9 0
10 0
11 0
3 1
7 1
10 1
12 1
12 2
11 12

Example output:
1
6
6
2
4
9
8
15
2
3
6
9
5
5

Editorial:
To begin with, let's solve it without queries and forced movements. Let's consider the nature of the path. The current vertex $$$v$$$ has a parent of parent $$$u$$$. Let there be an odd move now, and the robot will go to the parent of $$$v$$$. If we're lucky, it'll go to $$$u$$$. Otherwise, it will go to the brother of vertex $$$v$$$. But this won't change anything — the next step the robot will do the same thing again. For vertex $$$v$$$ and all its brothers, the answer is the same. Let $$$d[v]$$$ be the answer for vertex $$$v$$$, and let $$$x$$$ be the number of brothers of vertex $$$v$$$, including itself. Then $$$d[v] = 2 + \frac{1}{d + 1} \cdot d[u] + \frac{d}{d + 1} \cdot d[v]$$$, whence $$$d[v] = d[u] + 2 \cdot (x + 1)$$$.
We can see that our path consists of blocks of height $$$2$$$ — the robot tries to overcome the next block until it succeeds, and then proceeds to the next one.
We are now ready to answer the queries. Performing an operation is essentially skipping a block — the robot will pass it on the first try, spending not $$$2 \cdot (x + 1)$$$ actions on it, but $$$2$$$. Therefore we will delete blocks with the largest $$$x$$$ greedily. We will traverse the graph and store two sets of degrees of vertices on the path to the root — one for vertices with odd depth, and the other for vertices with even depth. We will answer requests offline. Having detected a query, we will run through the first $$$p$$$ elements of the corresponding set and subtract them.
Asymptotics of the trivial implementation, in which for each query we move up to the root, is $$$O(n \cdot q)$$$.
Asymptotics of a possible offline solution, where we will maintain sets of vertices while traversing the graph, is $$$O(n + \sum_i{p_i} \cdot set)$$$.