选择任意一个点做树的树的root...统计每个点的子树元素个数情况..对于不是root的点..将所有点数n减去当前子树的元素个数num.作为该点的另一个孩子...
program:
#include#include#include#include#include#include#include#include#include#define oo 1000000007#define ll long long#define pi acos(-1.0)#define maxn 50005using namespace std; struct node{ int x,y,next;}line[maxn*2]; int n,ansnum,ansdata,ans[maxn],_next[maxn];bool used[maxn];void addline(int x,int y,int m){ line[m].next=_next[x],_next[x]=m; line[m].x=x,line[m].y=y; return;}int dfs(int x){ int maxsub=0,num=0,t,k; k=_next[x]; while (k) { if (!used[line[k].y]) { used[line[k].y]=true; t=dfs(line[k].y); maxsub=max(t,maxsub); num+=t; used[line[k].y]=false; } k=line[k].next; } maxsub=max(maxsub,n-(num+1)); if (maxsub==ansdata) ans[++ansnum]=x; else if (maxsub