# CCPC2017 湘潭邀请赛 H Highway（树的直径）

## Highway

In ICPCCamp there were n towns conveniently numbered with 1,2,…,n connected with (n−1) roads. The i-th road connecting towns ai and bi has length ci. 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) cents, where δ(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.

### Input

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 ai, bi and ci.

• $1≤n≤10^{5}$
• $1≤a_{i},b_{i}≤n$
• $1≤c_{i}≤10^{8}$
• The number of test cases does not exceed 10.

### Output

For each test case, output an integer which denotes the result.

### Sample Input

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

### Sample Output

19
15

### 代码

// 没交，仅供参考

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int maxn = 100010;
ll dist1[maxn], dist2[maxn];
bool vis[maxn];
int n, cnt;

struct Edge
{
int to, next, w;
}edge[maxn];

void addedge(int u, int v, int w)
{
edge[cnt].to = v;
edge[cnt].w = w;
}

void dfs(int u, ll d, ll dist[])
{
dist[u] = d;
vis[u] = true;
for (int i = head[u]; i != -1; i = edge[i].next)
{
if (!vis[edge[i].to])
dfs(edge[i].to, d + edge[i].w, dist);
}
}

int main()
{
int u, v, w, d1, d2;
ll sum, maxdist;
while(scanf("%d", &n) != EOF)
{
cnt = 0;
for (int i = 0; i < n - 1; ++i)
{
scanf("%d%d%d", &u, &v, &w);
}
memset(vis, 0, sizeof(vis));
maxdist = 0;
dfs(1, 0, dist1); // 任一点开始bfs得到端点d1
for (int i = 1; i <= n; ++i)
{
if (dist1[i] > maxdist)
{
maxdist = dist1[i];
d1 = i;
}
}
memset(vis, 0, sizeof(vis));
maxdist = 0;
dfs(d1, 0, dist1); // 从端点d1开始得到端点d2
for (int i = 1; i <= n; ++i)
{
if (dist1[i] > maxdist)
{
maxdist = dist1[i];
d2 = i;
}
}
sum = dist1[d2];
memset(vis, 0, sizeof(vis));
dfs(d2, 0, dist2);
for (int i = 1; i <= n; ++i)
{
if (i != d1 && i != d2)
sum += max(dist1[i], dist2[i]); // 到两个端点中距离最大的
}
printf("%lld\n", sum);
}
return 0;
}

The end.
2018-05-06 星期天