#P18429. Easy Diameter Problem
Easy Diameter Problem
Easy Diameter Problem
Randias 有一棵包含 个顶点的树。他不断执行下面的操作,直到树中没有顶点:
- 选择当前树中某一条直径的一个端点,将这个顶点及其相连的边删除。
请计算不同删除顺序的数量,对 取模。
两个删除顺序不同,当且仅当存在 (),使这两个顺序中第 个被删除的顶点不同。
回顾:如果存在顶点 ,使得对于当前树中任意两个顶点 ,都有 ,那么 就是某一条直径的端点。这里 表示从 到 的最短路径上的边数。直径可以有多条,每一步可以选择其中任意一条的端点。当只剩一个顶点时,该顶点满足上述定义,可以被删除。
输入格式
第一行包含一个整数 (),表示树的顶点数。
接下来 行,每行包含两个整数 (,),表示连接 和 的一条边。保证这些边构成一棵树。
本题输入只有一棵树,没有测试组数。
输出格式
输出一个整数,表示不同删除顺序的数量对 取模的结果。
样例 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
样例说明
对于第一个样例,四种合法删除顺序为 、、、。