分数: 2000 点
问题陈述
对于无向树 t,让我们定义一个有理数 f(t) 如下。
- 让 n 是顶点数 t.
- If n=1:让 f(t)=1.
- If n \geq 2:
- 对于边缘 e in t,我们表示为 t_x(e) 和 t_y(e) 删除后产生的两棵树 e 来自 t (任意顺序)。
- 让 f(t)=(\sum_{e \in t} f(t_x(e)) \times f(t_y(e)))/n.
你得到一棵树 T 与 N 顶点编号 1 to N。 的 i第一条边连接顶点 A_i 和顶点 B_i.
查找值 f(T) \text{mod }{998244353}.
什么是有理数 \text{mod }{998244353}?
在本问题的约束下,当求的有理数表示为 \frac{P}{Q},可以证明 Q \neq 0 \pmod{998244353}。因此,存在一个唯一的整数 R 这样 R \times Q \equiv P \pmod{998244353}, 0 \leq R < 998244353。找到这个 R.
约束
- 2 \leq N \leq 5000
- 1 \leq A_i,B_i \leq N
- 给定的图是一棵树。
输入
输入由标准输入按以下格式给出:
N
A_1 B_1
A_2 B_2
\vdots
A_{N-1} B_{N-1}
输出
打印答案。
示例输入 1
2 1 2
示例输出 1
499122177
我们有 f(T)=1/2.
示例输入 2
3 1 2 2 3
示例输出 2
332748118
我们有 f(T)=1/3.
示例输入 3
4 1 2 2 3 3 4
示例输出 3
103983787
示例输入 4
10 4 5 1 9 6 1 8 4 5 9 4 7 3 10 5 2 4 3
示例输出 4
462781191