2019.2.12 Problem B - room

2019.2.12 Problem B - room

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给定一棵\(n\)个节点的树,节点编号为\(1 \sim n\),每条边的长度均为1。你想要选取三个节点,使它们两两间距离相同,求总的方案数。不区分三个节点的顺序,即\(\{1,2,3\}\)与\(\{2,1,3\}\)是同一种方案。

输入格式

第一行一个正整数\(n\);
接下来\(n-1\)行,每行两个整数\(u,v\),表示点\(u\)与点\(v\)之间有一条边。输入保证是一棵树。

输出格式

一个非负整数,表示所求的方案数。

样例

输入

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

输出

5

样例说明

样例中的5种方案为\(\{1,3,5\},\quad\{2,4,6\},\quad\{2,4,7\},\quad\{2,6,7\},\quad\{4,6,7\}\)。

数据规模、时空限制

对于20%的数据,\(n \le 50\)
对于50%的数据,\(n \le 500\)
对于100%的数据,\(n \le 5000\)
时间限制1s,空间限制512MB。

来源

2019.2 TYWZ提高组集训
供题人:于剑

2019.2.12测验

未参加
状态
已结束
规则
OI
题目
3
开始于
2019-02-12 14:00
结束于
2019-02-12 17:30
持续时间
3.5 小时
主持人
参赛人数
31