AT_agc058_f [AGC058F] Authentic Tree DP

对于一棵无向树 $t$，定义有理数 $f(t)$ 如下： - 设 $t$ 的顶点数为 $n$。 - 当 $n=1$ 时：$f(t)=1$。 - 当 $n \geq 2$ 时： - 对于 $t$ 的每一条边 $e$，将 $e$ 从 $t$ 中删除后得到的两棵树分别记为 $t_x(e), t_y(e)$（顺序无关）。 - $f(t) = \left( \sum_{e \in t} f(t_x(e)) \times f(t_y(e)) \right) / n$。 给定一棵有 $N$ 个顶点、顶点编号为 $1$ 到 $N$ 的树 $T$。第 $i$ 条边连接顶点 $A_i$ 和顶点 $B_i$。 请计算 $f(T)$ 的值，并对 $998244353$ 取模。 有理数 $\bmod\ 998244353$ 的定义：在本题的约束下，设所求有理数为最简分数 $\frac{P}{Q}$，可以证明 $Q \not\equiv 0 \pmod{998244353}$。因此，存在唯一的整数 $R$ 满足 $R \times Q \equiv P \pmod{998244353},\ 0 \leq R < 998244353$。请输出这个 $R$。

输入按以下格式从标准输入给出： > $N$ > $A_1$ $B_1$ > $A_2$ $B_2$ > $\vdots$ > $A_{N-1}$ $B_{N-1}$

请输出答案。

### 限制 - $2 \leq N \leq 5000$ - $1 \leq A_i, B_i \leq N$ - 输入的图保证是一棵树 ### 样例解释 1 $f(T) = 1/2$。 ### 样例解释 2 $f(T) = 1/3$。 由 ChatGPT 4.1 翻译