题目：http://pat.zju.edu.cn/contests/pat-a-practise/1021
题解：
给N个点，N-1条边，先判断是否为树，如果不是树，输出有几块；如果是树，求符合条件的i是哪些(当第i个节点为树根时，树的高度最大)。
先用并查集求所给的是否为树，然后通过两次dfs求最长的树径，第二次dfs时就可以记录符合条件的i，最后结合第一次和第二次的结果，从小到大排序输出。
注：测试数据中有n=1的情况。
代码：
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<string>
#include<vector>
#include<set>
#include<algorithm>
using namespace std;
#define MAX 10005
int edge[MAX<<1];//表示第i条边的终点
int nextx[MAX<<1];//与第i条边同起点的下一条边的位置
int head[MAX<<1];//以i为起点的第一条边的储存位置
int pre[MAX];
bool visited[MAX];
int n;
int maxDeep;
int point;
set<int> q,out;
void insert(int i,int a,int b)//a起点,b终点
{
edge[i]=b;
nextx[i]=head[a];
head[a]=i;
}
int Find(int x)//查找
{
if(pre[x]==x) return x;
return pre[x]=Find(pre[x]);
}
void Union(int a,int b)//合并
{
int x=Find(a);
int y=Find(b);
if(x!=y)
pre[y]=x;
}
void dfs(int st,int deep)
{
if(deep>maxDeep)
{
maxDeep=deep;
point=st;
q.clear();
q.insert(st);
}
else if(deep==maxDeep)
q.insert(st);
visited[st]=true;
for(int i=head[st]; i!=-1; i=nextx[i])
{
if(visited[edge[i]]==false)
dfs(edge[i],deep+1);
}
visited[st]=false;
}
int main()
{
int a,b;
int countx=0;
set<int>::iterator iter;
scanf("%d",&n);
for(int i=0; i<=n; ++i)
pre[i]=i;
memset(nextx,-1,sizeof(nextx));
memset(head,-1,sizeof(head));
memset(edge,-1,sizeof(edge));
for(int i=1; i<2*n-1; i+=2)
{
scanf("%d%d",&a,&b);
Union(a,b);
insert(i,a,b);
insert(i+1,b,a);
}
for(int i=1; i<=n; ++i)
if(pre[i]==i)
++countx;
if(countx>1)
{
printf("Error: %d components\n",countx);
return 0;
}
if(n==1)
{
printf("1\n");
return 0;
}
memset(visited,false,sizeof(visited));
maxDeep=0;
dfs(1,0);
memset(visited,false,sizeof(visited));
for(iter=q.begin();iter!=q.end();++iter)
{
out.insert(*iter);
}
q.clear();
maxDeep=0;
a=point;
dfs(point,0);
for(iter=q.begin();iter!=q.end();++iter)
{
out.insert(*iter);
}
out.insert(a);
for(iter=out.begin();iter!=out.end();++iter)
{
printf("%d\n",*iter);
}
return 0;
}