3041920_ac_78ms_852k.c

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int n, f, r, m;
int cnt[20005], pos[20005];
int visited[20005], que[20005], pa[20005];

struct node
{
	int s, e;
}edge[20005*2];

int cmp(const void *a,const void *b)
{
	struct node *aa = (struct node *)a;
	struct node *bb = (struct node *)b;

	return aa->s - bb->s;
}

void solve()
{
	int i, j, tt;
	int min, minv, tmp;

	f = 1;
	r = 2;
	visited[1] = 1;
	que[1] = 1;
	while(f < r)
	{
		for(i = pos[que[f]]; i < pos[que[f]+1]; i++)
		{
			if(visited[edge[i].e])	continue;
			visited[edge[i].e] = 1;
			que[r] = edge[i].e;
			pa[edge[i].e] = que[f];
			r++;
		}
		f++;
	}
	for(i = n; i > 1; i--)
	{
		cnt[que[i]] ++;
		cnt[pa[que[i]]] += cnt[que[i]];
	}
	cnt[1]++;
	tmp = -1;
	for(j = pos[1]; j < pos[2]; j++)
	{
		if(cnt[edge[j].e] > tmp)
		{
			tmp = cnt[edge[j].e];
		}
	}
	min = tmp;minv = 1;
	for(i = 2; i <= n; i++)
	{
		tmp = -1;
		for(j = pos[i]; j < pos[i+1]; j++)
		{
			if(edge[j].e==pa[i])
			{
				tt = n-cnt[i];
			}
			else
			{
				tt = cnt[edge[j].e];
			}
			if(tt > tmp)
			{
				tmp = tt;
			}
		}
		if(tmp < min)
		{
			min = tmp;
			minv = i;
		}
	}
	printf("%d %d\n",minv,min);
}

int main()
{
	int t, i;
	
	scanf("%d",&t);
	while(t--)
	{
		memset(cnt,0,sizeof(cnt));
		memset(visited,0,sizeof(visited));
		scanf("%d",&n);
		m = n-1;
		for(i = 1; i <= m; i++)
		{
			scanf("%d%d",&edge[i].s,&edge[i].e);
			edge[i+m].s = edge[i].e;edge[i+m].e = edge[i].s;
		}
		m <<= 1;
		qsort(&edge[1],m,sizeof(edge[1]),cmp);
		for(i = m; i > 0; i--)
		{
			pos[edge[i].s] = i;
		}
		pos[n+1] = m+1;
		solve();
	}
	return 0;
}