这个题目，WA的很郁闷阿。 哪位大牛给点提示吧？
code:
#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;
int n, len;
int f[50005];
int ans[55];
typedef struct
{
    int x, y;
}A;
A dis[100005];
int sp[50005];

bool cmp( A a, A b )
{
    return a.x < b.x;
}

int top, M;
int dfs( int v, int p )
{
    int Max = 0, sum = 0;
    int i = sp[v];
    do
    {
        if( dis[i].y != p )
        {
            int t = dfs( dis[i].y, v );
            if( t > Max )Max = t;
            sum += t;
        } 
        i++;
    }while( i < len && v == dis[i].x );
    if( n-1-sum > Max )Max = n-1-sum;
    f[v] = Max;
    return (sum+1);
}

int main()
{
    int x, y;
    while( EOF != scanf( "%d", &n ) )
    {
        len = 0;
        for( int i = 1; i < n; i++)
        {
            scanf( "%d%d", &x, &y);
            dis[len].x = x;
            dis[len++].y = y;
            dis[len].x = y;
            dis[len++].y = x;
        }
        sort(dis,dis+len,cmp);
        dis[len].x = -1;
        sp[dis[0].x] = 0;
        for( int i = 1; i < len; i++ )
        {
            if( dis[i].x != dis[i-1].x )
            {
                sp[dis[i].x] = i;
            }
        }
        dfs( 1, -1 );
        top = 1;
        M = 1;
        ans[0] = 1;
        for( int i = 2; i <= n; i++ )
        {
            if( f[i] < f[M] )
            {
                top = 1;
                ans[0] = i;
                M = i;
            }
            else if( f[i] == f[M] )
            {
                ans[top++] = i;
            }
        }
        printf( "%d",ans[0]);
        for(int i = 1; i < top; i++ )
        {
            printf( " %d", ans[i] );
        }
        printf( "\n" );
    }
    return 0;
}

• 喜欢做树形DP的，快来搞搞这个题目吧 。。。。。。。。。。。。。。。。。。。。。。。。。 (0) whitesea 2008-07-24 20:33:13