pku1655.cpp

来自「这是ACM 方面的资料 是PKU的 北京大学的出来的」· C++ 代码 · 共 92 行

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

typedef struct nodee
{
	int id;
	struct nodee * next;
} Node;

Node nd[20001];
int st[20001];
int SZ, N;

void Insert(int h, int k)
{
	Node *p;
	p = &nd[h];
	while (p->next != NULL)
	{
		p = p->next;
	}
	p->next = (Node *)malloc(SZ);
	p = p->next;
	p->id = k;
	p->next = NULL;
}

int DFS(int id)
{
	Node *p;
	int sum, max, tmp;
	sum = 1;
	max = 0;
	p = nd[id].next;

	while (p != NULL)
	{
		if (st[p->id] == 0)
		{
			st[p->id] = 1;
			tmp = DFS(p->id);
			sum += tmp;
			max = (max > tmp) ? max : tmp;
		}
		p = p->next;
	}
	tmp = N - sum;
	nd[id].id = (max > tmp) ? max : tmp;
//	printf("Id = %d sum = %d max = %d tmp = %d\n", id, sum, max, tmp);
	return sum;
}

int main()
{
	int T, i, s, e, minid, tmp, min;
	Node *p;
//	freopen("PKU1655.in", "r", stdin);
	scanf("%d", &T);
	SZ = sizeof(nd[0]);

	while (T--)
	{
		scanf("%d", &N);
		for (i = 1; i <= N; i++)
		{
			nd[i].id = i;
			nd[i].next = NULL;
			st[i] = 0;
		}
		for (i = 0; i < N - 1; i++)
		{
			scanf("%d %d", &s, &e);
			Insert(s, e);
			Insert(e, s);
		}

		minid = 1;
		st[1] = 1;
		min = DFS(1);
		for (i = 1; i <= N; i++)
		{
			if (nd[i].id < min)
			{
				min = nd[i].id;
				minid = i;
			}
		}
		printf("%d %d\n", minid, min);
	}
	return 0;
}