1.求树的最大直径

#include <iostream>
#include <string.h>

using namespace std;
const int N=1e5+5;
int h[N],e[N*2],ne[N*2],w[N*2],idx;

long long maxu,maxd;
void add(int a,int b,int c){
    e[idx]=b;
    w[idx]=c;
    ne[idx]=h[a];
    h[a]=idx++;
}
void dfs(int u,int fa,int d){//记录父节点，防止出现环路
    for(int i=h[u];i!=-1;i=ne[i]){
        int j=e[i];
        if(j==fa) continue;

        if(maxd<w[i]+d){
            maxd=w[i]+d;
            maxu=j;
        }
        dfs(j,u,d+w[i]);
    }
}
int main()
{
    int n;
    cin>>n;
    memset(h,-1,sizeof h);
    for(int i=0;i<n-1;i++){
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
        add(b,a,c);
    }
    //求树的直径，先随便选定一个点，求离其最远的点u，再求离u最远的距离
    dfs(1,-1,0);//起点的父节点为-1
    dfs(maxu,-1,0);
    cout<<(maxd+1)*maxd/2+10*maxd<<endl;
    //cout << "Hello world!" << endl;
    return 0;
}