解题思路
两次dfs求树的直径
AC代码
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N=1e5+10,M=2*N;
typedef long long LL;
int e[M],h[N],ne[M],idx,w[M];
int n;
int dist[N];
void add(int a,int b,int c)
{
e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
void dfs(int u,int father,int distance)
{
dist[u]=distance;
for(int i=h[u];~i;i=ne[i])
{
int j=e[i];
//如果不往回走
if(j!=father)
{
dfs(j,u,distance+w[i]);
}
}
}
int main()
{
cin>>n;
memset(h,-1,sizeof h);
for(int i=0;i<n-1;i++)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
add(a, b, c);
add(b,a,c);
}
dfs(1,-1,0);
int u=1;
for(int i=2;i<=n;i++)
if(dist[u]<dist[i])
u=i;
dfs(u,-1,0);
for(int i=1;i<=n;i++)
if(dist[u]<dist[i])
u=i;
int s=dist[u];
//1的LL转换
LL route=10*s+s*(s+1ll)/2;
cout<<route;
return 0;
}