1021 Deepest Root

这道题的关键在于如何求两个最远的结点，二叉树比较容易一直DFS就能找到，但是普通树就比较麻烦。要先找到一端，再去找另外一端，两端的并集就是答案。因为结点都是对称的，所以两端都是答案。还要注意去重，12 13这种就会重复。

#include<bits/stdc++.h>

using namespace std;

const int maxn = ;

vector<int>pre[maxn];

int n;

bool vis[maxn];

vector<int>ans;

void DFS(int s)

{

    int i;

    vis[s] = true;

    for (i =;i<pre[s].size(); i++)

    {

        if (vis[pre[s][i]] == false)

        {

            DFS(pre[s][i]);

        }

    }

    return;

}

vector<int>temp;

int maxh = ;

void find(int s,int height)//寻找以s为根距离s最远的结点,height为s距离该节点的距离.

{

    if (vis[s] == true)

        return;

    vis[s] = true;

    if (height > maxh)

    {

        temp.clear();

        temp.push_back(s);

        maxh = height;

    }

    else if (height == maxh)

    {

        temp.push_back(s);

    }

    int i;

    for (i = ; i < pre[s].size(); i++)

    {

        find(pre[s][i], height + );

    }

}

int main()

{

    scanf("%d", &n);

    int i, j;

    for (i = ; i <= n-; i++)

    {

        int st, ed;

        scanf("%d %d", &st,&ed);

        pre[st].push_back(ed);

        pre[ed].push_back(st);

    }

    memset(vis, false, sizeof(vis));

    int sum = ;

    for (i = ; i <= n; i++)

    {

        if (vis[i] == false)

        {

            sum++;

            DFS(i);

        }

    }

    if (sum >=)

    {

        printf("Error: %d components\n", sum);

    }

    else if (n == )

    {

        printf("%d\n", );

    }

    else

    {

        memset(vis, false, sizeof(vis));

        find(, );//此时temp里面已经装了若干边缘结点

        ans = temp;

        memset(vis, false, sizeof(vis));

        maxh = ;

        temp.clear();

        find(ans[], );

        for (i = ; i < temp.size(); i++)

        {

            ans.push_back(temp[i]);

        }

        sort(ans.begin(), ans.end());

        printf("%d\n", ans[]);

        for (i = ; i <ans.size(); i++)

        {

            if(ans[i]!=ans[i-])

            printf("%d\n",ans[i]);

        }

    }

}