思路：这个题其实就是找树的最大直径，两遍dfs就可以
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn=50000+50;
vector<pair<int,int> >g[maxn];
int vis[maxn];
int d1[maxn];
int idx1,idx2;
int ma1,ma2;
void dfs1(int u,int t)
{
if(vis[u])
return ;
vis[u]=1;
for(int i=0; i<g[u].size(); i++)
{
int v=g[u][i].first;
int c=g[u][i].second;
if(vis[v])
continue;
if(t+c>ma1)
{
ma1=t+c;
idx1=v;
}
dfs1(v,t+c);
}
}
void dfs2(int u,int t)
{
if(vis[u])
return;
vis[u]=1;
for(int i=0; i<g[u].size(); i++)
{
int v=g[u][i].first;
int c=g[u][i].second;
if(vis[v])
continue;
if(t+c>ma2)
{
ma2=t+c;
idx2=v;
}
dfs2(v,t+c);
}
}
int main()
{
int n;
cin>>n;
idx1=0;
idx2=0;
for(int i=0; i<n-1; i++)
{
int x,y,c;
cin>>x>>y>>c;
g[x].push_back(make_pair(y,c));
g[y].push_back(make_pair(x,c));
}
ma1=-1,ma2=-1;
dfs1(1,0);
memset(vis,0,sizeof(vis));
dfs2(idx1,0);
long long ans=ma2*10+ma2*(1+ma2)/2;
cout<<ans<<endl;
}
