题目地址：202.197.224.59/OnlineJudge2/
来自湘潭大学OJ，题号：1267。
这里用到了一个树的直径（树中的最长边）的结论：当你找到一棵树的最长边后，这个树中所有点的最长边必定和这条边的两个端点相连。下面给出证明：
设这条最长边的两个端点分别为B和E；
1.当选择的任意点M在这条最长边上时：如果此时还存在另一个点T，使得MT > max{MB,ME}。则：MT + min{MB,ME} > max{MB,ME} + min{MB,ME} = BE这与题目假设相矛盾。
2.当选择的任意点M不在这条最长边上时：
Α.与它相连的最长边与BE有交点时，假设交于X，则：M的最长边 = MX + X的最长边，而X在BE上，所以M的最长边 = MX + max{XB，XE}即它的最长边终止于BE中的一个点。
B.若无交点，假设M的最长边为MN，则：取BE上一点X，连接MX，有：MN > max{XB,XE} + XM，MN + MX + max{XB,XE} > 2MX + 2max{XB,XE} > BE与题设矛盾
由此，本题思路即为：先找到最长边，然后将其余的n - 2个点到最长边两个端点的距离算出，不断地挑选这n-2个点到两个端点的更长的那个路径，最后加上这条最长路就是所求结果。
下面的代码用C++11提交能过，而用G++则会WA
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#define maxn 100005
#define F 0x3f
using namespace std;
struct edge
{
int len,over;
edge(int a = ,int b = )
{
len = a,over = b;
}
};
long long dist[][maxn];
vector<edge> graph[maxn];
inline void init()
{
for(int i = ;i < maxn;++i)
graph[i].clear();
}
queue<int> q;
void bfs(int use,int start)
{
while(q.size()) q.pop();
q.push(start);
dist[use][start] = ;
while(q.size()){
int temp = q.front();
q.pop();
for(int i = ;i < graph[temp].size();++i){
int length = graph[temp][i].len,nextone = graph[temp][i].over;
if(dist[use][nextone] == -){
dist[use][nextone] = dist[use][temp] + length;
q.push(nextone);
}
}
}
return;
}
int main()
{
int n;
while(scanf("%d",&n) == ){
int start,over,len;
init();
for(int i = ;i < n - ;++i){
scanf("%d%d%d",&start,&over,&len);
graph[start].push_back(edge(len,over));
graph[over].push_back(edge(len,start));
}
int point1,point2;
memset(dist,-,sizeof(dist));
//printf("now dist is %lld\n",dist[0][0]);
bfs(,);
long long maxone = ;
for(int i = ;i <= n;++i){
if(dist[][i] > maxone) maxone = dist[][i],point1 = i;
}
maxone = ;
bfs(,point1);
for(int i = ;i <= n;++i){
if(dist[][i] > maxone) maxone = dist[][i],point2 = i;
}
bfs(,point2);
//printf("point1 is %d and point2 is %d\n",point1,point2);
long long answer = ;
answer += dist[][point2];
for(int i = ;i <= n;++i){
if(i != point1 && i != point2){
answer += max(dist[][i],dist[][i]);
}
}
if(n == ) answer = ;
printf("%lld\n",answer);
}
return ;
}