记录编号 16058 评测结果 WWWWW
题目名称 烟花的寿命 最终得分 0
用户昵称 Gravatarlc 是否通过 未通过
代码语言 C++ 运行时间 0.767 s
提交时间 2010-04-19 11:39:58 内存使用 4.11 MiB
显示代码纯文本
#include<iostream>
#include<cstring>
using namespace std;
const int maxn = 1003;
int Test,N,Maxd,V;
int Lis[maxn][maxn];
int Stack[maxn],Path[maxn];
bool vis[maxn];


void Addedge(int x,int y)
{
	Lis[x][++Lis[x][0]] = y;
}

void prep()
{
	scanf("%d",&N);
	for (int i=1; i<=N; i++) Lis[i][0] = 0;
	for (int i=1; i< N; i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		Addedge(x,y); Addedge(y,x);
	}
}

void DFs(int u,int d)
{
	if (vis[u]) return;
	vis[u] = true; Stack[d] = u;
	if (d >Maxd)
	{
		Maxd = d; V = u;
		memcpy(Path,Stack,sizeof(int)*(d+1));
	}
	for (int i=1; i<=Lis[u][0]; i++)
	{
		DFs(Lis[u][i],d+1);
	}
}

void work()
{
	memset(vis,0,sizeof(bool)*(N+1));
	Maxd = -1; DFs(1,0);
	memset(vis,0,sizeof(bool)*(N+1));
	Maxd = -1; DFs(V,0);
	printf("%d\n",Maxd);
	for (int i=0; i<=Maxd; i++)
		printf("%d\n",Path[i]);
}

int main()
{
	freopen("firework.in","r",stdin);
	freopen("firework.out","w",stdout);
	scanf("%d",&Test);
	while (Test--)
	{
		prep();
		work();
	}
	return 0;
}