IzIy's Files

题目描述

给定一张包含N个点、N-1条边的无向连通图，节点从1到N编号，每条边的长度均为1。从1号节点出发并打算遍历所有节点，那么总路程至少是多少？

输入

第一行包含一个整数N，1<=N<=10^5

接下来N-1行，每行包含两个整数X和Y，表于X号节点和Y号节点之间有一条边，1<=X，Y<=N。

输出

输出总路程的最小值。

样例输入

4
1 2
1 3
3 4

样例输出

4

解题思路：

从题目描述来看姑且可以将题目输入看做是树，以根节点开始遍历，计算总路程。

关键在于如何判断最短路径。分析可知，除最后一个遍历的叶子节点到根节点的弧只需走一遍外，其它所有弧都要走两遍。

因此，只需要计算出树的深度为D。

结果为 ：

[N-1)*2 - (D-1)

编码待续。