Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

物是人非~

Posted by cyy1308947278 at 2016-05-25 19:22:01 on Problem 3107
#include<map>
#include<vector>
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define N 55555
#define INF 0x3f3f3f3f
struct node
{
	int to,next;
}Edge[N<<1];
int head[N],n,cnt,num[N],ans,Min;
int vec[N],Size;
void add(int w,int v)
{
	Edge[cnt].to=v;
	Edge[cnt].next=head[w];
	head[w]=cnt++;
	
	Edge[cnt].to=w;
	Edge[cnt].next=head[v];
	head[v]=cnt++;
}
void Tree_DP(int w,int fa)
{
	int i,j,k,tot=0,Max=-1;
	for(i=head[w];~i;i=Edge[i].next)
	{
		int v=Edge[i].to;
		if(v==fa)continue;
		//printf("%d  %d \n",w,v);
		Tree_DP(v,w);
	
		num[w]+=num[v];	
	}
}
void dfs(int w,int fa)
{
//	printf("w=====%d %d",w,fa);
	int i,j,k,tot=0,Max=-1;
	for(i=head[w];~i;i=Edge[i].next)
	{
		int v=Edge[i].to;//printf("w==%d  %d \n",w,v);
		if(v==fa)continue;
		
		dfs(v,w);	
		Max=max(Max,num[v]);
		tot+=num[v];	
	}
	Max=max(Max,n-1-tot);
	if(Max<Min)
	{
		Min=Max;
		Size=0;
		vec[Size++]=w;
	}
	else if(Max==Min)
	vec[Size++]=w;
//	vec.push_back(w);
}
int main()
{
	int m,j,i,k,l;
	while(~scanf("%d",&n))
	{
		Size=0;
		memset(head,-1,sizeof(head));
		cnt=0;
		for(i=1;i<n;i++)
		scanf("%d%d",&j,&k),add(j,k),num[i]=1;
		num[n]=1;
		Min=INF;
		
		Tree_DP(1,0);
		dfs(1,0);
		
		sort(vec,vec+Size);
		for(i=0;i<Size;i++)
		{
			printf("%d",vec[i]);
			if(i!=Size-1)
			printf(" ");
			else 
			printf("\n");
		}
	}
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator