两次dfs

C++ 代码

#include<iostream>
#include<cstring>
using namespace std;
const int N = 202000;
int e[N],w[N],ne[N],h[N],idx=0;
int visited[N],far; //far为最远点
long long Max=0; //最远距离

void add(int a,int b,int c){
    e[idx]=b; w[idx]=c; ne[idx]=h[a]; h[a]=idx++;
}

void dfs(int a,int value){ //a为当前点，value为当前距离
    visited[a] = 1;
    if(value > Max){  //更新最远点和距离
        Max = value;
        far = a;
    }
    for (int i = h[a]; i != -1; i = ne[i] ){    
        if(!visited[e[i]])dfs(e[i], value+w[i]);
    }
}

int main(){
    int n,a,b,c;
    cin>>n;
    memset(h,-1,sizeof(h));
    for(int i=0; i<n-1; i++){
        cin>>a>>b>>c;
        add(a,b,c);
        add(b,a,c);
    }
    dfs(1,0);
    memset(visited,0,sizeof(visited));
    dfs(far,0);
    cout<<Max * 10 + (Max + 1) * Max / 2;
    return 0;
}