题目描述
在一片风平浪静的海域中,有 $n$ 个岛屿,有 $n-1$ 条道路将它们相连,但是,由于某些特殊的原因,原来的双向道路全部都毁坏了一半,也就是变成了单向道路,现在每一座岛屿的权值定义为从该岛屿出发可以到达的岛屿数(包括自身),整片海域的权值定义为所有岛屿的权值的积,然而又因为一些特殊的原因,和这些岛屿之间的联系也被切断了,所以你并不知道道路具体的方向,于是你想知道对于所有可能的海域的情况的权值的和,由于答案可能很大,你只需要给出答案对 $998244353$ 取模的结果。
输入格式
从 sea.in
中读入数据。
第一行,一个数 $n$,表示树的节点数。
第二行至第 $n$ 行,每行两个数 $u_i,v_i$ ,表示树上的一条边。
输出格式
输出到 sea.out
中。
一行,一个整数,所有情况下的树的权值和。
输入样例 1
4
1 2
2 3
2 4
输出样例 1
102
输入输出样例 2
见选手目录下的 ex_sea.in/out
数据规模
对于 $100\%$ 的数据,满足 $1\leq n\leq 400,1\leq u_i,v_i\leq n,u_i\neq v_i$,满足给出的图是一棵树。
子任务如下表所示:
子任务编号 | $n$ | 特殊性质 | 分值 |
---|---|---|---|
1 | $\leq 15$ | - | 3 |
2 | $\leq 40$ | - | 12 |
3 | $\leq 80$ | - | 30 |
4 | - | A | 10 |
5 | - | B | 10 |
6 | - | - | 35 |
特殊性质 A:保证 $\forall 1 \leq i< n,u_i=i,v_i=i+1$。
特殊性质 B:保证 $\forall 1\leq i< n,u_i=1$。