树形dp
dp[i][0]=(i的全部员工的max(dp[u][1],dp[u][0)相加，也就是其子员工来或不来的最大快乐值。
dp[i][1]=(i的全部员工的dp[u][0相加，也就是其子员工都不能不来的最大快乐值。
#include <cstdio> #include <iostream> #include <cstring> #include <algorithm> #include <vector> #define int long long using namespace std; typedef long long LL; #define mst(s, t) memset(s, t, sizeof(s)) const int INF = 0x3f3f3f3f; const int maxn = 10010; vector<int> G[maxn]; int A[maxn]; int dp[maxn][2]; int n; void dfs(int node, int father) { //若是叶子结点则return sum=1，否则求其子树(包括自己)的总结点数 dp[node][0]=0; dp[node][1]=A[node]; for(int i=0; i<G[node].size(); i++) { if(G[node][i] == father)continue; //因为是树结构，这里可以在无向时避免遍历成环 dfs(G[node][i],node); dp[node][0]+=max(dp[G[node][i]][0], dp[G[node][i]][1]); dp[node][1]+=dp[G[node][i]][0]; } return ; } signed main() { //freopen("in.txt", "r", stdin); scanf("%I64d", &n); for(int i=1; i<=n; i++) { scanf("%I64d",&A[i]); } int a,b; while(scanf("%I64d%I64d", &a, &b)) { if(a==b&&a==0)break; G[a].push_back(b); G[b].push_back(a); } dfs(1, 0); cout<<max(dp[1][0],dp[1][1])<<' '; //cout << n << "==" << tmp << endl; //验证 return 0; }