/*--------------------------------------------------------------------------------------*/
//		Helica's header 
//		Second Editions
//		2015.11.7
//
#include <algorithm>
#include <iostream>
#include <cstring>
#include <ctype.h>
#include <cstdlib>
#include <cstdio>
#include <vector>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <set>
#include <map>

//debug function for a N*M array 
#define debug_map(N,M,G) printf("\n");for(int i=0;i<(N);i++)\
{for(int j=0;j<(M);j++){\
printf("%d",G[i][j]);}printf("\n");}				
//debug function for int,float,double,etc.
#define debug_var(X) cout<<#X"="<<X<<endl;
/*--------------------------------------------------------------------------------------*/
using namespace std;

const int maxn = 200010;
int N,M,T,kase;
int maxsubtree[maxn],sons[maxn];
bool vis[maxn];

struct Edge{
	int to,next;
}edge[2*maxn];

int head[maxn],tot;

void dfs(int u)
{
	vis[u] = 1;
	sons[u] = 1;
	for(int i=head[u];i != -1;i = edge[i].next)
	{
		int v = edge[i].to;
		if(vis[v]) continue;
		dfs(v);
		sons[u] += sons[v];
		maxsubtree[u] = max(sons[v],maxsubtree[u]);
	}
	maxsubtree[u] = max(maxsubtree[u],N-sons[u]);
}

void addedge(int u,int v)
{
	edge[tot].to = v;
	edge[tot].next = head[u];
	head[u] = tot++; 
}

int main()
{
	scanf("%d",&T);
	while(T--)	
	{
		memset(vis,0,sizeof vis);
		memset(head,-1,sizeof head);
		memset(maxsubtree,0,sizeof maxsubtree);
		scanf("%d",&N);
		for(int i=1;i<N;i++)
		{
			int u,v;
			scanf("%d%d",&u,&v);
			addedge(u,v);
			addedge(v,u);
		}
		dfs(1);
		int id,size=maxn;
		for(int i=1;i<=N;i++)
		{
			if(size > maxsubtree[i]) 
			{
				id = i;
				size = maxsubtree[i];
			}
		}
		printf("%d %d\n",id,size);
	}
}

• Re:maxn开20010RE，200010就能过了，简直逗我 (45) 571678424 2018-05-26 15:33:42
• Re:maxn开20010RE，200010就能过了，简直逗我 (1974) xsly 2020-08-16 11:45:45