经典dp。。不多说啦。因为他是n-1条边，所以不用考虑森林的情况
# include <iostream> # include <cstdio> # include <algorithm> # include <cstring> # include <vector> # define inf -0x7ffffff using namespace std; typedef struct NODE{ int k;struct NODE* next; }Node; Node edge[7000],*tail=edge,*G[7000]; void add(int a,int b) { tail->k = b;tail->next = G[a];G[a] = tail++; } int v[7000],vis[7000],d[7000][2]; int dp(int u,int f) { if (d[u][f]!=inf) return d[u][f]; Node* i; if (f) d[u][f] = v[u]; else d[u][f] = 0; if (f) for (i=G[u];i;i=i->next) d[u][f] += dp(i->k,0); else for (i=G[u];i;i=i->next) d[u][f] += max(dp(i->k,0),dp(i->k,1)); return d[u][f]; } int main() { int n,i,a,b,t; scanf("%d",&n); for (i=0;i<7000;++i) { d[i][0] = inf; d[i][1] = inf; } for (i=1;i<=n;++i) scanf("%d",&v[i]); for (i=0;i<n-1;++i) { scanf("%d%d",&a,&b); add(b,a); vis[a] = 1; } scanf("%d%d",&a,&b); for (i=1;i<=n;++i) if (!vis[i]) t = i; printf("%d ",max(dp(t,1),dp(t,0))); return 0; }