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≤105
1≤ai,bi≤n
1≤ci≤108
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

比较明显的，一个点到树上最远距离的点，必然是树的直径上的点。

所以我们两次bfs求出树的直径，然后把树的直径加入到答案中，然后把其他的点到树的直径的最大值加入到树的直径中即可。

AC代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int n,d1[N],d2[N],p1,p2,res;
int head[N],nex[N<<1],to[N<<1],w[N<<1],tot;
inline void add(int a,int b,int c){
    to[++tot]=b; w[tot]=c; nex[tot]=head[a]; head[a]=tot;
}
inline void init(){
    memset(head,0,sizeof head); tot=0;    res=0;
    memset(d1,0,sizeof d1);	memset(d2,0,sizeof d2);
}
int bfs(int s){
    int vis[N]={0}; queue<int> q;   q.push(s); vis[s]=1;    int t=s,mx=0;
    while(q.size()){
        int u=q.front();    q.pop();
        for(int i=head[u];i;i=nex[i]){
            if(vis[to[i]])  continue;
            vis[to[i]]=vis[u]+w[i]; 	q.push(to[i]);
			if(vis[to[i]]>mx)   mx=vis[to[i]],t=to[i]; 
        }
    }
    return t;
}
void bfs1(int s,int d[]){
	d[s]=1;	queue<int> q;	q.push(s);
	while(q.size()){
		int u=q.front();	q.pop();
		for(int i=head[u];i;i=nex[i]){
			if(d[to[i]])	continue;
			d[to[i]]=d[u]+w[i];	q.push(to[i]);
		}
	}
}
signed main(){
    while(~scanf("%lld",&n)){
        init();
        for(int i=1;i<n;i++){
            int a,b,c;  scanf("%lld %lld %lld",&a,&b,&c); add(a,b,c); add(b,a,c);
        }
        p1=bfs(1);	p2=bfs(p1);	bfs1(p1,d1);	bfs1(p2,d2);
        for(int i=1;i<=n;i++)	res+=max(d1[i],d2[i])-1;
        printf("%lld\n",res-d1[p2]+1);
    }
    return 0;
}