给你一棵有 $$$n$$$ 个顶点的树。
让我们将机器人放置在某个顶点 $$$v \ne 1$$$ 中,并假设我们最初有 $$$p$$$ 硬币。考虑以下过程,其中第 $$$i$$$ 步骤(从 $$$i = 1$$$ 开始):
- 如果 $$$i$$$ 为奇数,则机器人沿顶点 $$$1$$$ 方向移动到相邻顶点;
- 否则,$$$i$$$ 是偶数。你可以支付一枚硬币(如果还有剩余的话),然后机器人向顶点$$$1$$$方向移动到相邻顶点,或者不支付,然后机器人移动到统一随机选择的相邻顶点。
一旦机器人到达顶点$$$1$$$,该过程就会停止。如果我们以最佳方式使用我们的代币,则令 $$$f(v, p)$$$ 为上述过程中可能的最小预期步骤数。
回答 $$$q$$$ 查询,在第 $$$i$$$ 中,您必须找到 $$$f(v_i, p_i)$$$ 的值,模 $$$^{\text{*}}$$$ $$$998\,244\,353$$$。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^3$$$)。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$2 \le n \le 2 \cdot 10^3$$$; $$$1 \le q \le 2 \cdot 10^3$$$) - 树中的顶点数和查询数。
接下来的 $$$n - 1$$$ 行包含树的边,每行一条边。第 $$$i$$$ 行包含两个整数 $$$u_i$$$ 和 $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$; $$$u_i \neq v_i$$$),表示节点 $$$u_i$$$ 和 $$$v_i$$$ 之间的边。
接下来的 $$$q$$$ 行包含两个整数 $$$v_i$$$ 和 $$$p_i$$$ ($$$2 \le v_i \le n$$$; $$$0 \le p_i \le n$$$)。
保证给定的边形成一棵树。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10 ^ 3$$$。
保证所有测试用例的 $$$q$$$ 总和不超过 $$$2 \cdot 10 ^ 3$$$。
输出
对于每个测试用例,打印 $$$q$$$ 整数:$$$f(v_i, p_i)$$$ 模 $$$998\,244\,353$$$ 的值。
正式地,令 $$$M = 998\,244\,353$$$。可以证明,答案可以表示为不可约分数 $$$\frac{p}{q}$$$,其中 $$$p$$$ 和 $$$q$$$ 是整数,$$$q \not \equiv 0 \pmod{M}$$$。输出等于 $$$p \cdot q^{-1} \bmod M$$$ 的整数。换句话说,输出一个整数$$$x$$$,使得$$$0 \le x < M$$$ 且$$$x \cdot q \equiv p \pmod{M}$$$。
示例
输入 #1
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
输出 #1
1 6 6 2 4 9 8 15 2 3 6 9 5 5
注意
第一个测试用例中的树:
在第一个查询中,预期值等于 $$$1$$$,因为机器人在第一步中开始从顶点 $$$2$$$ 移动到顶点 $$$1$$$ 并且过程停止。
让我们计算第二个查询中的期望值($$$x$$$ 是步数):
- $$$P(x < 2) = 0$$$,到顶点$$$1$$$的距离是$$$2$$$,机器人无法以更少的步数到达它。
- $$$P(x = 2) = \frac{1}{3}$$$,因为只有一个步骤序列导致 $$$x = 2$$$。这是 $$$3 \rightarrow_{1} 2 \rightarrow_{0.33} 1$$$,概率为 $$$1 \cdot \frac{1}{3}$$$。
- $$$P(x \bmod 2 = 1) = 0$$$,因为机器人只需采取偶数步即可到达顶点 $$$1$$$。
- $$$P(x = 4) = \frac{2}{9}$$$:可能的路径 $$$3 \rightarrow_{1} 2 \rightarrow_{0.67} [3, 4] \rightarrow_{1} 2 \rightarrow_{0.33} 1$$$。
- $$$P(x = 6) = \frac{4}{27}$$$:可能的路径 $$$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}$$$ 在一般情况下。
因此,$$$f(v, p) = \sum\limits_{i=1}^{\infty}{i \cdot 2 \cdot \frac{2^{i - 1}}{3^i}} = 6$$$。
第二个测试用例中的树: