蓝桥杯 大臣的旅费

#include <bits/stdc++.h>

using namespace std;
#define maxn 1000000 + 10

struct edge
{
    int v, dist;
};

int n;
int index = 1;
int M = -1;
vector<edge>G[maxn];
bool vis[maxn] = {false};

void DFS(int u, int dist)
{
    if(dist > M)
    {
        index = u;
        M = dist;
    }
    vis[u] = true;
    for(int i=0; i<G[u].size(); i++)
    {
        edge &e = G[u][i];
        if(!vis[e.v])
            DFS(e.v, dist + e.dist);
    }
    vis[u] = false;
    return ;
}

int main()
{
    cin>>n;
    int u, v, dist;
    for(int i=1; i<n; i++)
    {
        cin>>u>>v>>dist;
        G[u].push_back(edge{v, dist});
        G[v].push_back(edge{u, dist});
    }
    DFS(index, 0);

    DFS(index, 0);
    cout<<10 * M + (M + 1) * M / 2<<endl;
    return 0;
}

蓝桥杯 大臣的旅费

原文：http://blog.csdn.net/dojintian/article/details/44946975