← 返回题目列表

AtCoder · agc058_f

F. 正宗树DP

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

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