← 返回题目列表

AtCoder · arc217_e

E. 树生长

中文机器翻译题面 查看原题

分数: 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.