SP1437 PT07Z

树的直径的模板题。

1. 从任意一个节点出发（以(1)号点为例），找出距离(1)号点最远的点(p)，(p)为直径的一个端点
2. 将(d[p])清(0)，找出距离(p)最远的点(q)，((p, q)) 即为直径的两个端点，(d[q])即为树的直径长度

const int N=10010;
vector<int> g[N];
int d[N];
int n;
int far;

void dfs(int u,int fa)
{
    for(int i=0;i<g[u].size();i++)
    {
        int j=g[u][i];
        if(j == fa) continue;
        d[j]=d[u]+1;
        if(d[j] > d[far])
            far=j;
        dfs(j,u);
    }
}

int main()
{
    cin>>n;

    for(int i=0;i<n-1;i++)
    {
        int a,b;
        cin>>a>>b;
        g[a].pb(b);
        g[b].pb(a);
    }

    dfs(1,-1);
    d[far]=0;
    dfs(far,-1);
    cout<<d[far]<<endl;

    //system("pause");
    return 0;
}