NC52867 Highway （树的直径定理）

题目描述
In ICPCCamp there were n towns conveniently numbered with 1,2,…,n1, 2, \dots, n1,2,…,n
connected with (n - 1) roads.
The i-th road connecting towns aia_iai​ and bib_ibi​ has length cic_ici​.
It is guaranteed that any two cities reach each other using only roads.

Bobo would like to build (n - 1) highways so that any two towns reach each using only highways.
Building a highway between towns x and y costs him δ(x,y)\delta(x, y)δ(x,y) cents,
where δ(x,y)\delta(x, y)δ(x,y) is the length of the shortest path between towns x and y using roads.

As Bobo is rich, he would like to find the most expensive way to build the (n - 1) highways.

输入描述:
The input contains zero or more test cases and is terminated by end-of-file. For each test case:

The first line contains an integer n.
The i-th of the following (n - 1) lines contains three integers aia_iai​, bib_ibi​ and cic_ici​.

• 1≤n≤1051 \leq n \leq 10^51≤n≤105
• 1≤ai,bi≤n1 \leq a_i, b_i \leq n1≤ai​,bi​≤n
• 1≤ci≤1081 \leq c_i \leq 10^81≤ci​≤108
• The number of test cases does not exceed 10.

输出描述:
For each test case, output an integer which denotes the result.
思路：
参考Mr_Kingk大佬的博客

树的直径定理：
1、树上距离任意一点最远的点一定是端点
2、距离端点最远的点一定为另一端点

等价于任意两点间的边长被定义为两点间路径的长度，求最大生成树。
某点到其他点的最长的路径长度，一定是到该树的两个端点之一的距离。
故，就要将每个点都连接在两个端点上。两个端点之间靠直径相连，完成一棵最大生成树。

那么如何找端点呢？
以1为根节点，找到所有其他点到1的距离，其中距离最长的点，就是端点。
再以端点为根节点，找到距离端点最远的点，这个点就是另一个端点。
接着，针对某一个点，选择连接到哪一个端点上。
选择哪一个呢？
当然是距离自己最远的端点了！
最后要记得将res减去直径，因为直径被两个端点各加了一遍，所以要减去一遍。
示例1
输入

5
1 2 2
1 3 1
2 4 2
3 5 1
5
1 2 2
1 4 1
3 4 1
4 5 2
1
2
3
4
5
6
7
8
9
10

输出

19
15
1
2

代码：

#include
#include
using namespace std;
#define int long long
const int N=2e5+10, M=2 * N;
long long dist1[N],dist2[N];    
int h[N], e[M], w[M],ne[M], idx;

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
void dfs(int u,long long dist[])
{
	for(int i=h[u];i!=-1;i=ne[i])
	{
		int j=e[i];
		if(dist[j]==-1)
		{
			dist[j]=dist[u]+w[i];
			dfs(j,dist);
		}
	}
}
signed main()
{
	int n;
	ios::sync_with_stdio(false);
    cin.tie(0);
	while(cin>>n)
	{
		memset(h,-1,sizeof h);
		idx=0;
		for(int i=0;i<n-1;i++)
		{
			int a,b,c;
			cin>>a>>b>>c;
			add(a,b,c);
			add(b,a,c);
		}
		memset(dist1,-1,sizeof dist1);
		dist1[1]=0;
		dfs(1,dist1);
		int first=-1;
		long long mx=-1;
		for(int i=1;i<=n;i++)
		{
			if(dist1[i]>mx)
			{
				mx=dist1[i];
				first=i;
			}
		}
		memset(dist1,-1,sizeof dist1);
		dist1[first]=0;
		dfs(first,dist1);
		int second=-1;
		mx=-1;
		for(int i=1;i<=n;i++)
		{
			if(dist1[i]>mx)
			{
				mx=dist1[i];
				second=i;
			}
		}
		memset(dist2,-1,sizeof dist2);
		dist2[second]=0;
		dfs(second,dist2);
		long long res=0;
		for(int i=1;i<=n;i++)
		{
			res+=max(dist1[i],dist2[i]);
		}
		res-=mx;
		cout<<res<<endl;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78