DFS暴力破解

#include <iostream>
#include <algorithm>

using namespace std;

int h[10010][10010];
int ans,nummax;
int n;

int check(int start,int last,int before,int numcount){
    if(h[start][last]>0){
        numcount=numcount+h[start][last];
        nummax=max(nummax,numcount);
        return h[start][last];
    }
    else{
        if(start!=last){
            for(int i=1;i<=n;i++){
                if(h[start][i]!=0&&i!=before&&start!=last){
                    check(i,last,start,numcount+h[start][i]);
                }
            }
        }
    }
}

int main()
{
    cin>>n;
    for(int i=0;i<n-1;i++){
        int a,b,juli;
        cin>>a>>b>>juli;
        h[a][b]=juli;
        h[b][a]=juli;
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++){
            check(i,j,0,0);
        }

    for(int i=1;i<=nummax;i++){
        ans+=i+10;
    }
    cout<<ans;


    return 0;
}

改进版：

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

int ans,nummax;
int n,pnt1;

class Point{
public:
    int pointnum,cost;
};

void dfs(vector<Point> m[],int vis[],int start,int dis){
    vis[start]=0;
    bool isleaf=true;
    for(int k=0;k<m[start].size();k++){
        int num = m[start][k].pointnum;
        if(vis[num]==-1){
            isleaf = false;
            dfs(m,vis,num,dis+m[start][k].cost);
        }
    }
    vis[start]=-1;
    if(isleaf){
        if(dis>nummax){
            nummax=dis;
            pnt1=start;
        }
    }
}

int main(){
    cin>>n;
    vector<Point> m[n+1];
    int vis[n + 1];
    memset(vis,-1,sizeof(vis));
    for(int i=0;i<n-1;i++){
        int a,b,juli;
        cin>>a>>b>>juli;
        Point p1 = {b,juli};
        Point p2 = {a,juli};
        m[a].push_back(p1);
        m[b].push_back(p2);
    }

dfs(m,vis,1,0);
dfs(m,vis,pnt1,0);
for(int i=1;i<=nummax;i++){
        ans+=i+10;
    }
cout<<ans;


    return 0;
}