http://poj.org/problem?id=2114
#include <vector>
#include <stdio.h>
#include <algorithm>
using namespace std;
typedef pair< int, int > edge;
vector< edge > e[10010];
int v[10010],s[10010];
int st[10010],sn;
bool sign[10010];
int n;
int find_root_search( int r, int f )
{
int temp,i,j;
v[r] = 0;
s[r] = 1;
st[sn++] = r;
for( i=0; i<e[r].size(); i++ )
{
j = e[r][i].first;
if( j != f && sign[j] )
{
temp = find_root_search( j , r );
if( temp > v[r] ) v[r] = temp;
s[r] += temp;
}
}
return s[r];
}
int find_root( int r, int f )
{
int i,h,j,t;
sn = 0;
h = find_root_search( r, f );
r = st[0];
for( i=0; i<sn; i++ )
{
j = st[i];
if( ( t = h - s[j] ) > v[j] ) v[j] = t;
if( v[j] < v[r] ) r = j;
}
return r;
}
int _dis[100],mm;
int dis[100],m;
int id[100];
int ans[10010],*temp=st,ans_n;
bool ok[100];
int cn;
void calc_dis( int r, int len, int f )
{
int i, j;
ans[cn++] = len;
for( i=0; i<e[r].size(); i++ )
{
j = e[r][i].first;
if( j != f && sign[j] )
{
calc_dis( j, len + e[r][i].second, r );
}
}
}
void search( int r, int num, int f, int len )
{
int i,j,h,a,num1,rr=r,t;
int *p1,*p2,*q1,*q2,*p;
ans[ans_n++] = 0;
sn = 0;
r = find_root( r, f );
sign[r] = false;
for( i=0; i<e[r].size(); i++ )
if( sign[ j = e[r][i].first ] )
{
h = e[r][i].second;
num1 = ans_n;
search( j, num1, r, h );
if( m == 0 )
return;
p1 = ans + num; q1 = ans + num1;
p2 = ans + num1; q2 = ans + ans_n;
if( q1-p1 > q2-p2 )
{
swap( p1, p2 );
swap( q1, q2 );
}
for( p=p1; p<q1; p++ )
{
for( a=0; a<m; a++ )
{
t = dis[a]-*p;
if( t >= *p2 && t<=*(q2-1) && binary_search( p2, q2, t ) )
{
ok[ id[a] ] = true;
dis[a] = dis[m-1];
id[a] = id[m-1];
m--;
a--;
}
}
}
merge( p1, q1, p2, q2, temp );
copy( temp, temp+ans_n-num, ans+num );
}
sign[r] = true;
cn = num;
calc_dis( rr, len, f );
sort( ans+num, ans+ans_n );
}
bool init()
{
int i,d,c;
scanf( "%d", &n );
if( n == 0 )return false;
for( i=0; i<n; i++ )
{
e[i].clear();
sign[i] = true;
}
for( i=0; i<n; i++ )
while( 1 )
{
scanf( "%d", &d );
if( d == 0 ) break;
scanf( "%d", &c );
e[i].push_back( edge( d-1, c ) );
e[d-1].push_back( edge( i, c ) );
}
m = 0;
while( 1 )
{
scanf( "%d", &dis[m] );
if( dis[m] == 0 )break;
_dis[m] = dis[m];
id[m] = m;
ok[m] = false;
m++;
}
mm = m;
ans_n = 0;
return true;
}
int main()
{
int i;
while( init() )
{
search( 0, 0, -1, 0 );
for( i=0; i<mm; i++ )
{
if( ok[i] ) printf( "AYEn" );
else printf( "NAYn" );
}
printf( ".n" );
}
return 0;
}