http://acm.pku.edu.cn/JudgeOnline/problem?id=3107题意：给定一棵无根树，删除树中一个节点，剩下各子树的包含的节点数最大值最小，问树中有多少个这样的节点?
解法：任意选择一个节点，作为根，进行遍历。对一个节点V，设其子节点为cv[1..k]，f[v]为以节点v为根的子树包含的节点数。
对
于每一个节点V，删除V之后剩下子树含有的节点数中最大分别为
max{ f[cv[1]]，f[cv[2]]，....f[cv[k]]，SumNode-(f[cv[1]]+f[cv[2]]+....+f[cv[k]])
}，一次遍历即可求出所有删除一个节点后的最大子树包含的节点数。
//7044398 Oestrus 3107 Accepted 4164K 688MS G++ 1595B 2010-06-11 22:11:19
#include<iostream>
#include<vector>
#include<algorithm>
#include<stdio.h>
#define MAXN 50005
using namespace std;
vector<int>ansNode;
int maxNumNode;
int n, f[MAXN];
int pointTree[MAXN];
struct Tree{
int x,y;
}tree[MAXN*2];
int len;
bool cmp(struct Tree a, struct Tree b)
{
return a.x<b.x;
}
int treedp(int parentNode,int thisNode){
int maxNode=0;
int sumChildNode=0;
int index=pointTree[thisNode];
do{
int childNode=tree[index].y;
if(childNode != parentNode)
{
f[childNode]=treedp(thisNode,childNode);
sumChildNode+=f[childNode];
if(f[childNode]>maxNode)maxNode=f[childNode];
}
index++;
}while(index<len && tree[index].x==tree[index-1].x);
if(maxNode<n-sumChildNode-1)maxNode=n-sumChildNode-1;
if(maxNode<maxNumNode){
maxNumNode=maxNode;
ansNode.clear();
ansNode.push_back(thisNode);
}else if(maxNode==maxNumNode){
ansNode.push_back(thisNode);
}
return sumChildNode+1;
}
int main(int argc,int *argv[])
{
while(scanf("%d",&n)!=EOF){
len=0;
for(int i=1;i<n;i++){
int x,y;
scanf("%d%d",&x,&y);
tree[len].x=x;
tree[len++].y=y;
tree[len].x=y;
tree[len++].y=x;
}
sort(tree,tree+len,cmp);
pointTree[tree[0].x]=0;
for(int i=1;i<len;i++){
if(tree[i].x != tree[i-1].x)
pointTree[tree[i].x] = i;
}
ansNode.clear();
maxNumNode=n;
treedp(-1,1);
sort(ansNode.begin(),ansNode.end());
for(int i=0;i<ansNode.size();i++)
printf("%d ",ansNode[i]);
}
return 0;
}