HDU 1520 Anniversary party
d[i][0]=以i为根的子树，不选择i时的最大值 d[i][1]=以i为根的子树，选择i时的最大值
d[i][0]=∑v为i的儿子max(d[v][0],d[v][1]) d[i][1]=∑v为i的儿子d[v][0]
#include<stdio.h> #include <iostream> #include<stdlib.h> #include<algorithm> #include<vector> #include<deque> #include<map> #include<set> #include<queue> #include<math.h> #include<string.h> #include<string> using namespace std; #define ll long long #define pii pair<int,int> const int inf = 1e9 + 7; const int N = 1e6 + 5; struct Edge{ int v,next; }edge[2*N]; int head[N]; inline void addEdge(int k,int u,int v){ edge[k].v=v; edge[k].next=head[u]; head[u]=k; } int c[N]; int d[N][2]; int inDeg[N]; int dp(int i,int j){ if(d[i][j]>0){ return d[i][j]; } else{ d[i][j]=j?c[i]:0; for(int k=head[i];k!=-1;k=edge[k].next){ int v=edge[k].v; if(j==0){ d[i][j]+=max(dp(v,1),dp(v,0)); } else{ d[i][j]+=dp(v,0); } } } return d[i][j]; } int main() { //freopen("/home/lu/Documents/r.txt","r",stdin); //freopen("/home/lu/Documents/w.txt","w",stdout); int n; while(~scanf("%d",&n)){ for(int i=1;i<=n;++i){ d[i][0]=d[i][1]=-inf; head[i]=-1; scanf("%d",&c[i]); inDeg[i]=0; } int l,k; int nume=0; while(scanf("%d%d",&l,&k),l+k){ addEdge(nume++,k,l); ++inDeg[l]; } int ans=0; for(int i=1;i<=n;++i){ if(inDeg[i]==0){ ans+=max(dp(i,0),dp(i,1)); } } printf("%d\n",ans); } return 0; }