#include <iostream>#include <cstdio>#include <cstring>#include <cstdlib>#include <cmath>#include <map>#include <queue>#include <set>#include <vector>#define MOD 100000000#define LL __int64using namespace std;int dp[7000][2];struct node{    int u,v,next;}edge[7000];int first[7000];int flag[7000];int p[7000];int t;void CL(){    t = 0;    memset(first,-1,sizeof(first));}void add(int u,int v){    edge[t].u = u;    edge[t].v = v;    edge[t].next = first[u];    first[u] = t ++;}int dfs(int x,int st,int fa){    int sum = 0,i,v;    if(dp[x][st] != -1)    return dp[x][st];    for(i = first[x];i != -1;i = edge[i].next)    {        v = edge[i].v;        if(v == fa) continue;        dfs(v,0,x);        dfs(v,1,x);        if(st == 0)        sum += max(dp[v][0],dp[v][1]);        else        sum += dp[v][0];    }    if(st == 1)    return dp[x][1] = sum + p[x];    else    return dp[x][0] = sum;}int main(){    int n,i,u,v;    while(scanf("%d",&n)!=EOF)    {        CL();        memset(dp,-1,sizeof(dp));        for(i = 1;i <= n;i ++)        {            scanf("%d",&p[i]);        }        memset(flag,0,sizeof(flag));        for(;;)        {            scanf("%d%d",&u,&v);            if(!u&&!v) break;            add(v,u);            flag[u] = 1;        }        for(i = 1;i <= n;i ++)        {            if(!flag[i])            add(0,i);        }        printf("%d\n",dfs(0,0,-1));    }    return 0;}

#include <iostream>#include <cstdio>#include <cstring>#include <cstdlib>#include <cmath>#include <map>#include <queue>#include <set>#include <vector>#define MOD 100000000#define LL __int64using namespace std;int dp[10001][2];int ans[10001];int flag[10001];struct node{    int u,v,w,next;}edge[20001];int t;int first[10001];void CL(){    t = 1;    memset(first,-1,sizeof(first));}void add(int u,int v,int w){    edge[t].u = u;    edge[t].v = v;    edge[t].w = w;    edge[t].next = first[u];    first[u] = t ++;}void dfs1(int x){    int i,v,max1 = 0,max2 = 0;    flag[x] = 1;    for(i = first[x];i != -1;i = edge[i].next)    {        v = edge[i].v;        if(flag[v]) continue;        dfs1(v);        if(max1 < dp[v][0] + edge[i].w)        {            max2 = max1;            max1 = dp[v][0] + edge[i].w;        }        else if(max1 == dp[v][0] + edge[i].w)        max2 = dp[v][0] + edge[i].w;        else if(max2 < dp[v][0] + edge[i].w)        max2 = dp[v][0] + edge[i].w;    }    dp[x][0] = max1;    dp[x][1] = max2;}void dfs2(int x,int fa){    int i,v;    flag[x] = 1;    ans[x] = max(dp[x][0],fa);    for(i = first[x];i != -1;i = edge[i].next)    {        v = edge[i].v;        if(flag[v]) continue;        if(dp[x][0] == dp[v][0] + edge[i].w)        dfs2(v,max(fa,dp[x][1])+edge[i].w);        else        dfs2(v,max(fa,dp[x][0])+edge[i].w);    }}int main(){    int i,n,v,w;    while(scanf("%d",&n)!=EOF)    {        CL();        for(i = 2;i <= n;i ++)        {            scanf("%d%d",&v,&w);            add(v,i,w);            add(i,v,w);        }        memset(flag,0,sizeof(flag));        dfs1(1);        //for(i = 1;i <= n;i ++)        //printf("%d %d\n",dp[i][0],dp[i][1]);        memset(flag,0,sizeof(flag));        dfs2(1,0);        for(i = 1;i <= n;i ++)        printf("%d\n",ans[i]);    }    return 0;}

#include <cstdio>#include <cstring>#include <string>#include <iostream>using namespace std;#define INF 100000000struct node{    int u,v,next;}edge[1501];int dp[1501][2];int flag[1501];int t;int first[1501];void CL(){    t = 0;    memset(flag,0,sizeof(flag));    memset(dp,0,sizeof(dp));    memset(first,-1,sizeof(first));}void add(int u,int v){    edge[t].u = u;    edge[t].v = v;    edge[t].next = first[u];    first[u] = t ++;}void dfs(int x){    int i,v;    for(i = first[x];i != -1;i = edge[i].next)    {        v = edge[i].v;        dfs(v);    }    for(i = first[x];i != -1;i = edge[i].next)    {        v = edge[i].v;        dp[x][1] += min(dp[v][0],dp[v][1]);        dp[x][0] += dp[v][1];    }    dp[x][1] ++;}int main(){    int i,j,n,m,u,v;    while(scanf("%d",&n)!=EOF)    {        CL();        for(i = 1;i <= n;i ++)        {            scanf("%d:(%d)",&u,&m);            for(j = 1;j <= m;j ++)            {                scanf("%d",&v);                flag[v] = 1;                add(u,v);            }        }        for(i = 0;i < n;i ++)        {            if(!flag[i])            {                dfs(i);                printf("%d\n",min(dp[i][0],dp[i][1]));                break;            }        }    }    return 0;}