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

struct In 
{ 
int x; 
int y; 
}s[50001]; 

int flag[50001],num[50001],t;
int search(int n)
{
    int max,sum,i,temp;
    max=0;
    sum=0;
    for(i=0;i<t;i++)
    {
        if(s[i].x==n) 
        {
            temp=search(s[i].y);
            if(temp>max) max=temp;       
            sum+=temp;
        }
        if(s[i].x>n) break;       
    }
    flag[n]=max;
    num[n]=sum;
    return sum+1;
}

int cmp( const void *a , const void *b) 
{ 
struct In *c = (In *)a; 
struct In *d = (In *)b; 
if(c->x != d->x) return c->x - d->x; 
else return c->y - d->y; 
} 

int main()
{
    int i,j,pp,min;
    
    while(scanf("%d",&t)!=EOF)
    {
        s[0].x=0;
        s[0].y=1;
        for(i=1;i<t;i++)
        scanf("%d%d",&s[i].x,&s[i].y);
        qsort(s,t,sizeof(s[0]),cmp);
        memset(flag,0,sizeof(flag));
        search(0);
        
        for(i=1;i<=t;i++)
        if(flag[i]<(t-1-num[i])) flag[i]=(t-1-num[i]);
        
        min=flag[1];
        for(i=2;i<=t;i++)
        {
            if(min>flag[i]) min=flag[i];    
        } 
        
        pp=0;
        for(i=1;i<=t;i++)
        {
            if(min==flag[i]) 
            {
                if(pp==0) 
                {
                    printf("%d",i);
                    pp=1;    
                }
                else printf(" %d",i);
            }    
        }
        printf("\n");
    }
    return 0;    
}

• Re:为什么WA啊 大牛给看看 (1710) singlelove 2007-04-09 20:55:31