3369. 三千米健身步道

单点时限: 2.0 sec

内存限制: 256 MB

华师大是一个巨大的学校,众所周知,华师大的地图是一棵树,有 n 座教学楼,这些教学楼之间由 n1 条道路相连,每条道路的长度都是一千米。

现在华师大投资建设一个「三千米健身步道」。为了让同学们不带喘气的跑(走)完这个健身步道,这个健身步道必须有一个起点,一个终点,中间是一段连续的三千米的跑道。华师大决定利用现有的 n1 条道路建设这一个健身步道。问总共有多少种方案?

注意,起点和终点交换算同一种方案。

输入格式

第一行为 n (2n1000),表示教学楼数量,教学楼编号从 1n

接下来 n1 行,每行为 ui,vi (1ui,vin,uivi),表示 ui,vi 之间有道路相连。

输出格式

输出方案数。如果不存在,输出 0

样例

Input
6
1 2
2 3
3 4
4 5
4 6
Output
3

168 人解决,184 人已尝试。

216 份提交通过,共有 562 份提交。

2.3 EMB 奖励。

创建: 7 年,6 月前.

修改: 7 年,6 月前.

最后提交: 1 周,6 天前.

来源: 2017.9.27 ACM 选拔赛

题目标签