链接：https://www.icpc.camp/contests/4mYguiUR8k0GKE
H. Highway
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.
题意：
每次连接最远的两点，直到所有点都相通。
最多有n-1条边
题解：
如何每次都找到最远的两个点呢？
我们需要用到一个定理：树上的任何一个点的最远点一定会是<树的直径>中的一个。
树的直径指：树上的最远的两个点
接下来我们证明这个定理——
1，利用这个定理，我们可以从<1节点>dfs找到一个直径上的点。
2，用直径上的这个点dfs可以找到另外一个直径上的点。
3，找出所有点到这两个直径上的点的距离
4，将所有点都连接在直径的两个点之一，就是答案了
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int f[maxn],nex[2*maxn],w[2*maxn],tob[2*maxn],inde;
long long dis1[maxn],dis2[maxn];
bool vis[maxn];
long long s1,maxdis,s2;
long long madis=-1;
void add(int a,int b,int wn)
{
inde++;
tob[inde]=b;
w[inde]=wn;
nex[inde]=f[a];
f[a]=inde;
}
void dfs1(int x,long long v)
{
vis[x]=0;
for(int i=f[x];i;i=nex[i])
{
if(vis[tob[i]])
{
long long gg=v+w[i];
if(gg>madis)
{
madis=gg;
s1=tob[i];
}
dfs1(tob[i],gg);
}
}
}
void dfs2(int x,long long v)
{
vis[x]=0;
for(int i=f[x];i;i=nex[i])
{
if(vis[tob[i]])
{
long long gg=v+w[i];
if(gg>maxdis)
{
maxdis=gg;
s2=tob[i];
}
dis1[tob[i]]=gg;
dfs2(tob[i],gg);
}
}
}
void dfs3(int x,long long v)
{
vis[x]=0;
for(int i=f[x];i;i=nex[i])
{
if(vis[tob[i]])
{
long long gg=v+w[i];
dis2[tob[i]]=gg;
dfs3(tob[i],gg);
}
}
}
int main()
{
int n;
while(cin>>n)
{
inde=0;
for(int i=1;i<=n;i++)f[i]=0;
for(int i=1;i<n;i++)
{
int a,b,wn;
scanf("%d %d %d",&a,&b,&wn);
add(a,b,wn);
add(b,a,wn);
}
maxdis=madis=-1;
for(int i=1;i<=n;i++)vis[i]=1;
dfs1(1,0);
for(int i=1;i<=n;i++)vis[i]=1;
dfs2(s1,0);
for(int i=1;i<=n;i++)vis[i]=1;
dfs3(s2,0);
long long ans=maxdis;
for(int i=1;i<=n;i++)
{
if(i==s1||i==s2)continue;
ans+=max(dis1[i],dis2[i]);
}
cout<<ans<<endl;
}
return 0;
}