树的直径

求树的直径DFS

两次DFS,第一次随便一个点的最远点(这个最远点就是直径的一端)，第二次这个最远点再找到一个最远点即可

#include<iostream>
#include<cstring>
using namespace std;

const int N = 1010;
int h[N],e[N*2],ne[N*2],w[N*2],idx;
void add(int a,int b,int c)
{
    e[idx]=b;
    w[idx]=c;
    ne[idx]=h[a];
    h[a]=idx++;
}
int root,max_len;
bool st[N];
void dfs(int x,int len)
{
    st[x]=true;
    if(len>max_len){
        root=x;
        max_len=len;
    }
    for(int i=h[x];i!=-1;i=ne[i]){
        int j=e[i];
        int c=w[i];
        if(!st[j]){
            dfs(j,len+c);
            st[j]=false;
        }
    }
}
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);
    }
    dfs(1,0);
    memset(st,false,sizeof st);
    dfs(root,0);
    cout<<max_len<<endl;
}