#P17736. 公交线路

公交线路

题目描述

给定一棵 nn 个点的无根树。我们希望在一些点对之间修建公交线路,满足任意两个点之间只需要至多两条公交线路就能到达。

形式化地说,考虑树上的所有 n(n−1)2\frac{n(n-1)}2 条两个端点不同的简单路径。对于这些路径的一个子集 SS,称它是好的当且仅当:

  • 考虑一张新的图 GG,对于一对点 u,vu,v,当且仅当存在 SS 中的一条路径 PP,满足 uu 和 vv 都在 PP 上,我们会在 u,vu,v 之间连上边权为 11 的无向边。
  • 要求 GG 中任意两点之间的距离都不超过 22。

你需要求出有多少个子集 SS 是好的。由于答案可能很大,输出对 998244353998244353 取模的结果。

输入格式

第一行,一个正整数 nn 表示节点个数。接下来 n−1n-1 行,每行两个正整数 u,vu,v,表示一条树边 (u,v)(u,v)。

输出格式

输出一个整数,表示答案对 998244353998244353 取模的结果。

样例输入 1

3
1 2
2 3

样例输出 1

5

样例输入 2

6
1 2
2 3
2 4
3 5
3 6

样例输出 2

27296

样例解释 1

对于第一个样例,所有可行的方案为 {(1,3)}\{(1,3)\}、{(1,3),(1,2)}\{(1,3),(1,2)\}、{(1,3),(2,3)}\{(1,3),(2,3)\}、{(1,3),(1,2),(2,3)}\{(1,3),(1,2),(2,3)\}、{(1,2),(2,3)}\{(1,2),(2,3)\}。

测试点约束

对于所有的数据,保证 1≤n≤30001\le n\le 3000。

测试点编号 n≤n\le 特殊性质
1∼31\sim3 66 无
4∼74\sim7 1010
8∼108\sim10 30003000 A
11∼1411\sim14 100100 无
15∼1815\sim18 500500
19∼2019\sim20 30003000

特殊性质 A:保证树是一条链。