蓝桥杯_ 历届试题 大臣的旅费

思路：这个题其实就是找树的最大直径，两遍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;

}