题目链接
做这道题的时候有点颓了 有思路后，看的题解才A掉
这里写代码片 #include<cstdio> #include<cstring> #include<iostream> using namespace std; const int INF=0x33333333; const int N=6050; struct node{ int x,y,nxt; }; node way[N<<1]; int n,R[N],st[N],tot=0; int f[N]; bool son[N]; void add(int u,int w) { tot++; way[tot].x=u;way[tot].y=w;way[tot].nxt=st[u];st[u]=tot; } int doit(int now) { int i,j,k; int f1=0,f2=0; if (f[now]<INF) return f[now]; if (st[now]==0) return R[now]; for (i=st[now];i;i=way[i].nxt) f1+=doit(way[i].y); for (i=st[now];i;i=way[i].nxt) { j=way[i].y; for (k=st[j];k;k=way[k].nxt) f2+=doit(way[k].y); } return f[now]=max(f1,f2+R[now]); } int main() { scanf("%d",&n); memset(f,0x33,sizeof(f)); for (int i=1;i<=n;i++) scanf("%d",&R[i]); for (int i=1;i<n;i++) { int u,w; scanf("%d%d",&u,&w); add(w,u); son[u]=1; } int root; for (int i=1;i<=n;i++) if (!son[i]) //不是儿子 { root=i; break; } printf("%d",doit(root)); return 0; }