好久没更了。前段时间去ec-final，实力水一波，混了个铜，虽然很弱，但是可以算是对之前一段时间的回报吧。
现在每天忙着复习，逃课太多，啥都不会。。。不想挂科啊！！Orz...
题意（简化）：警察想抓捕黑手党老大。现在警察们认为黑手党内部是树形结构，每个人看做节点。删除一个节点，这棵树就分为几个连同分量。现在对于每个节点，删去后得到的连同分量的最大值为t。t的值最小的是哪些人，都输出。
解法:对于节点，他的最大连同分量只可能来自2方面，他的孩子方向或者他的父亲方向。只要判断一下大小即可。
#include<cstdio>
#include<cstring>
#include<vector>
#include<iostream>
using namespace std;
const int MAXN = ;
struct node{
int to;
int next;
}edge[MAXN*];
int index,vis[MAXN],pre[MAXN],n;
int num[MAXN],dp[MAXN],way[MAXN],ans[MAXN];
void add(int x,int y)
{
edge[index].to = y;
edge[index].next = pre[x];
pre[x] = index++;
}
void dfs1(int rt)
{
vis[rt] = ;
int i;
for(i=pre[rt]; i!=-; i=edge[i].next){
int v = edge[i].to;
if(!vis[v]){
dfs1(v);
if(dp[rt] < num[v]){
dp[rt] = num[v];
way[rt] = v;
}
num[rt] += num[v];
}
}
num[rt] += ;
}
void dfs2(int rt,int pa)
{
vis[rt] = ;
int i;
if(pa == -){
for(i=pre[rt]; i!=-; i=edge[i].next){
int v = edge[i].to;
if(!vis[v]){
ans[rt] =max(ans[rt], num[v]);
dfs2(v,rt);
}
}
}
else {
ans[rt] = n - num[rt];
for(i=pre[rt]; i!=-; i=edge[i].next){
int v = edge[i].to;
if(!vis[v]){
ans[rt] = max(ans[rt], dp[rt]);
dfs2(v,rt);
}
}
}
}
int main()
{
int i,j;
while(~scanf("%d",&n))
{
index = ;
memset(pre,-,sizeof(pre));
for(i=; i<n; i++){
int x,y;
scanf("%d%d",&x,&y);
add(x,y);
add(y,x);
}
memset(dp,,sizeof(dp));
memset(way,,sizeof(way));
memset(num,,sizeof(num));
memset(ans,,sizeof(ans));
memset(vis,,sizeof(vis));
dfs1();
memset(vis,,sizeof(vis));
dfs2(,-);
int v = ;
for(i=; i<=n; i++){
if(ans[i] != )
v = min(v,ans[i]);
}
int flag = ;
for(i=; i<=n; i++){
if(v == ans[i])
{
if(!flag){
printf("%d",i);
flag = ;
}
else printf(" %d",i);
}
}
cout<<endl;
}
}