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 whitesea at 2008-07-24 08:37:46 on Problem 3107
```这个题目，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;
}
```

Followed by:

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

Content:

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