#P18429. Easy Diameter Problem

Easy Diameter Problem

Easy Diameter Problem

Randias 有一棵包含 nn 个顶点的树。他不断执行下面的操作,直到树中没有顶点:

  • 选择当前树中某一条直径的一个端点,将这个顶点及其相连的边删除。

请计算不同删除顺序的数量,对 109+710^9+7 取模。

两个删除顺序不同,当且仅当存在 ii(1≤i≤n1\le i\le n),使这两个顺序中第 ii 个被删除的顶点不同。

回顾:如果存在顶点 vv,使得对于当前树中任意两个顶点 i,ji,j,都有 dis⁡(u,v)≥dis⁡(i,j)\operatorname{dis}(u,v)\ge\operatorname{dis}(i,j),那么 uu 就是某一条直径的端点。这里 dis⁡(x,y)\operatorname{dis}(x,y) 表示从 xx 到 yy 的最短路径上的边数。直径可以有多条,每一步可以选择其中任意一条的端点。当只剩一个顶点时,该顶点满足上述定义,可以被删除。

输入格式

第一行包含一个整数 nn(1≤n≤3001\le n\le300),表示树的顶点数。

接下来 n−1n-1 行,每行包含两个整数 u,vu,v(1≤u,v≤n1\le u,v\le n,u≠vu\ne v),表示连接 uu 和 vv 的一条边。保证这些边构成一棵树。

本题输入只有一棵树,没有测试组数。

输出格式

输出一个整数,表示不同删除顺序的数量对 109+710^9+7 取模的结果。

样例 1

3
1 2
3 2
4

样例 2

5
4 1
4 5
1 2
1 3
28

样例 3

7
5 7
2 5
2 1
1 6
3 6
4 1
116

样例说明

对于第一个样例,四种合法删除顺序为 [1,2,3][1,2,3]、[1,3,2][1,3,2]、[3,1,2][3,1,2]、[3,2,1][3,2,1]。