Logo Universal Online Judge

UOJ

时间限制:1 s 空间限制:1024 MB

#2026. 海域(sea)

统计

题目描述

​ 在一片风平浪静的海域中,有 $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$。

大样例