首页 › 题库 › C/C++编程考级 › C/C++编程七级 › 简答题
简答题 偏难
#13123

给定一棵包含 N个顶点的树。顶点编号为 1 至 N,第 i条边 (1≤i≤N−1) 连接顶点 ai与顶点 bi。 对于树中任意两个顶点 u 和 v(满足 u<v…

给定一棵包含 N个顶点的树。顶点编号为 1 至 N,第 i条边 (1≤i≤N−1) 连接顶点 ai与顶点 bi。

对于树中任意两个顶点 u 和 v(满足 u<v),定义距离 d(u,v)为连接 u 和 v的简单路径上的边的数量。

请计算所有满足 u<v的顶点对 (u,v) 的距离 d(u,v) 的总和。

输入格式

第一行 ,一个整数表示n

接下来的n−1行,每行两个整数ai,bi.

输出格式

输出所有满足 u<v的顶点对 (u,v) 的距离 d(u,v)的总和。


输入样例#1

3
1 2
2 3

输出样例#1

3

输入样例#2

5
1 2
1 3
1 4
1 5

输出样例#2

10

说明提示

【 数据范围 】

2≤N≤105

1≤ai,bi≤N

限制

时间限制:1000ms

内存限制:256MiB

未登录也能判分,登录后才会记录
答案与解析
正确答案:<p>答案整理中……<br/></p>
这道题暂未补解析。