分数: 900 点
问题陈述
你有一棵树 N 顶点编号 1 to N。在这里, N 至少 2。的 i第边缘 (1\le i\le N-1) 连接顶点 u_i 和 v_i.
在此树上准确执行以下操作 K 次。的 k第次操作 (1\le k\le K) 如下。
- 选择其中一项 N-2+k 树的边缘在该点均匀随机。让 u 和 v 是由所选边连接的顶点。准备一个新顶点 N+k,添加连接顶点的边 u 和 N+k 和连接顶点 v 和 N+k,然后删除所选边。
请注意,对于 k=1,2,\ldots,K,树将有 N+k 之后的顶点 k第次操作。
求期望值,模 998244353,属于 \displaystyle \sum_{1\le i < j\le N+K} \text{dist}(i,j) 之后 K 操作。在这里, \text{dist}(i,j) 表示顶点之间的距离 i 和 j 在树中。
你被给予 T 测试用例;解决它们中的每一个。
期望值的定义 \ \text{mod}\ 998244353
可以证明,要找到的期望值总是有理数。而且,在这个问题的约束下,当这个有理数表示为不可约分数时 \displaystyle \frac{P}{Q},可以证明 Q \neq 0 \bmod 998244353。因此,有一个唯一的整数 R 满意 R \times Q \equiv P \bmod 998244353, 0 \leq R \lt 998244353。找到这个 R.
约束
- 1\le T
- 2\le N
- 总和 N 所有测试用例最多 3\times 10^5.
- 1\le K
- 总和 K 所有测试用例最多 10^6.
- 1\le u_i < v_i \le N
- 给定的图是一棵树。
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
每个测试用例均按以下格式给出:
N K
u_1 v_1
u_2 v_2
\vdots
u_{N-1} v_{N-1}
输出
按顺序输出测试用例的答案,以换行符分隔。
示例输入 1
3 4 2 1 2 1 3 1 4 4 5 1 2 2 3 3 4 6 13 1 2 1 3 2 4 2 5 3 6
示例输出 1
499122208 120 713032723
考虑第一个测试用例。
例如,两个操作按如下方式进行。
- 操作 1:连接顶点的边 选择 1 和 2 。添加连接顶点的边后 1 和 5 和连接顶点 2 和 5,连接顶点的边 1 和 2 已删除。
- 操作 2:连接顶点的边 选择 2 和 5 。添加连接顶点的边后 2 和 6 和连接顶点 5 和 6,连接顶点的边 2 和 5 已删除。
在这种情况下,值 \displaystyle \sum_{1\le i < j\le N+K} \text{dist}(i,j) is 32.
的值 \displaystyle \sum_{1\le i < j\le N+K} \text{dist}(i,j) is 31 有概率 \displaystyle \frac12 和 32 有概率 \displaystyle \frac12.