This is my code, WA at test # 4:
====================================
#include <iostream>
#include <cstdlib>
using namespace std;
const int maxn=6000*128+1;
int l[6001],r[6001],rec[6001],parent[6001],p[6001][2],v[6001];
bool e[6001],ve[6001][2];
int solve(int x,int t)
{
    int t0,t1,sum(0);
    if(t)
    {
        sum=v[x];
        if(e[parent[x]])return -maxn;
        if(ve[x][t])return p[x][t];
        ve[x][t]=e[x]=1;
        if(l[x])
           sum+=solve(l[x],0);
        e[x]=0;
    }else
    {
        if(ve[x][t])return p[x][t];
        ve[x][t]=1;
        if(l[x])
           sum=solve(l[x],1);
    }
    if(r[x])
    {
           t0=solve(r[x],0);
           t1=solve(r[x],1);
           if(t0>t1)sum+=t0;
           else sum+=t1;
    }
    p[x][t]=sum;
    return sum;
}
int main(int argc, char *argv[])
{
    int i,j,n,x,y,s,t;
    bool bb(0);
    cin>>n;
    for(i=1;i<=n;i++)
        cin>>v[i];
    while(1)
    {
        cin>>x>>y;
        if(!x && !y)break;
        parent[x]=y;
        if(!l[y])
        {
           l[y]=x;rec[y]=x;
        }
        else
        {
           r[rec[y]]=x;rec[y]=x;
        }
    }
    for(i=1;i<=n;i++)
      if(!parent[i])
      {
           s=i;break;
      }
    for(i=1;i<=n;i++)
        for(j=0;j<2;j++)
            if(!l[i] && !r[i])
               {
                   ve[i][j]=1;
                   p[i][j]=j*v[i];
               }else p[i][j]=-maxn;
    solve(s,0);
    solve(s,1);
    if(p[s][0]>p[s][1])
        cout<<p[s][0]<<endl;
    else cout<<p[s][1]<<endl;
    //system("PAUSE");
    return 0;
}

I don't think there are non-negative convivialitys. my AC program didn't take care of it. Take this test (i think it's the same manner with test 4):
4
100
1
1
100
2 1
3 2
4 3
The answer it's 200 (not 101).

Edited by author 08.10.2004 00:02