Sgu/134

遍历树。 经典的题

#include <stdio.h>
#include <vector>
using namespace std;
#define INF 10000000
 
typedef vector<int> VI; 
 
int n, x, y, Size[16001], SonSize[16001];
VI adj[16001], centroid;
 
void dfs(int u, int fa)
{
     Size[u] = 1;
     for (int i = 0; i < adj[u].size(); ++i)
         if (adj[u][i] != fa)
         {
            int v = adj[u][i];
            dfs(v, u);
            Size[u] += Size[v];
            SonSize[u] = max(SonSize[u], Size[v]);
         }
}
 
int main()
{
    scanf("%d", &n);
    for (int i = 1; i < n; ++i)
    {
        scanf("%d %d", &x, &y);
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    dfs(1, 0);
    int ans = INF;
    for (int i = 1; i <= n; ++i)
    {
        int tmp = max(n - Size[i], SonSize[i]);
        if (tmp < ans)
        {
           ans = tmp;
           centroid.clear();
           centroid.push_back(i);
        }  
        else if (tmp == ans) 
             centroid.push_back(i);
    }
    printf("%d %d\n", ans, centroid.size());
    for (int i = 0; i < centroid.size(); ++i)
        printf("%d ", centroid[i]);
    return 0;
}
// From FingerSed

//by hza
#include<cstdio>
 
const int NUM=16000+10;
int n;
int s[NUM*2],t[NUM*2],next[NUM*2],begin[NUM],top;
int dp[NUM],fa[NUM],size[NUM],Max[NUM];
 
void addedge(int x,int y)
{
	s[++top]=x;t[top]=y;
	next[top]=begin[x];begin[x]=top;
}
 
void init()
{
	int i,x,y;
	scanf("%d",&n);
	for(i=1;i<=n-1;++i)
	{
		scanf("%d %d",&x,&y);
		addedge(x,y);addedge(y,x);
	}
}
 
void dfs(int u)
{
	size[u]=1;
	Max[u]=0;
	int i,v;
	for(i=begin[u];i;i=next[i])
	{
		v=t[i];
		if(size[v]==0)
		{
			fa[v]=u;
			dfs(v);
			size[u]+=size[v];
			if(size[v]>Max[u])Max[u]=size[v];
		}
	}
}
 
int max(int a,int b)
{
	return a>b?a:b;
}
 
int answer=100000000,tot;
 
void work()
{
	init();
	int i;
	dfs(1);
	for(i=1;i<=n;++i)
	{
		dp[i]=max(Max[i],n-size[i]);
		if(dp[i]<answer)
		{
			answer=dp[i];
			tot=1;
		}else if(dp[i]==answer)++tot;
	}
	printf("%d %d\n",answer,tot);
	for(i=1;i<=n;++i)
		if(dp[i]==answer)
			printf("%d ",i);
	printf("\n");
}
 
int main()
{
	freopen("134.in","r",stdin);
	freopen("134.out","w",stdout);
	work();
}