题目描述 Ural大学有N名职员，编号为1~N。他们的关系就像一棵以校长为根的树，父节点就是子节点的直接上司。每个职员有一个快乐指数，用整数 H_i 给出，其中 1≤i≤N。现在要召开一场周年庆宴会，不过，没有职员愿意和直接上司一起参会。在满足这个条件的前提下，主办方希望邀请一部分职员参会，使得所有参会职员的快乐指数总和最大，求这个最大值。 输入 第一行一个整数N。(1<=N<=6000) 接下来N行，第i+1行表示i号职员的快乐指数H_i。(-128<=H_i<=127) 接下来N-1行，每行输入一对整数L, K。表示K是L的直接上司。 最后一行输入0,0。 输出 输出最大的快乐指数 样例输入 Copy 7 1 1 1 1 1 1 1 1 3 2 3 6 4 7 4 4 5 3 5 0 0 样例输出 Copy 5
树形dp
#include<bits/stdc++.h> using namespace std; const int N=6100; int dp[N][2]; int a[N]; bool father[N]; int h[N],e[N],idx,ne[N]; int n; void add(int a,int b) { e[idx]=b; ne[idx]=h[a]; h[a]=idx++; } void dfs(int u) { dp[u][1]=a[u]; for(int i=h[u];i!=-1;i=ne[i]) { int j=e[i]; dfs(j); dp[u][0]+=max(dp[j][0],dp[j][1]); dp[u][1]+=dp[j][0]; } } int main() { cin>>n; memset(h,-1,sizeof(h)); for(int i=1;i<=n;i++) cin>>a[i]; for(int i=0;i<n-1;i++) { int a,b; cin>>a>>b; father[a]=true; add(b,a); } int root=1; while(father[root]) root++; dfs(root); printf("%d\n",max(dp[root][0],dp[root][1])); }