Poj Solution 2114

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;
}