C++树的直径求解代码

解题思路:根据题意发现从首都出发每个大城市只有一条路，所以可以确定 这个结构是一棵树，所以可以先求出树的直径（树中长度最长的路径），再算出费用

求出直径的步骤

1. 任取一点a

2. 对a做一遍深搜求出距离a最远的点b

3. 对b再做一次深搜找出距离b最远的点，b到这个点的距离就是树的直径
   

注意事项:
不过这个题目暴力对每个点dfs其实可以拿到80分了
参考代码:

#include<bits/stdc++.h>

#define int long long

const int N =1e5+5;

//走一千米是 1+10 走两千米是 1+10+2+10 即x!+x*10

using namespace std;

bool vis[N];

typedef pair<int,int> pii;

int p1,d=0,ans;

vector<pii> m[N];

void dfs1(int u,int h){

    vis[u]=1;

    if(h>d){

        d=h;

        p1=u;

    }

    for(auto i:m[u]){

        if(vis[i.first])continue;

        dfs1(i.first,h+i.second);

    }

}

void dfs2(int u,int h){

    vis[u]=1;

    if(h>d){

        d=h;

    }

    for(auto i:m[u]){

        if(vis[i.first])continue;

        dfs2(i.first,h+i.second);

    }

}

signed main()

{   

    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    int n; cin>>n;

    for(int i=1;i<n;i++){

        int a,b,c; cin>>a>>b>>c;

        m[a].push_back({b,c});

        m[b].push_back({a,c});

    }

    dfs1(1,0);

    d=0;

    memset(vis,0,sizeof(vis));

    dfs2(p1,0);

    for(int i=1;i<=d;i++){

        ans+=i;

    }

    ans+=(d*10);

    cout<<ans<<endl;

    return 0;

}