题目描述
某大学有 n 个职员，编号为 1…n。
他们之间有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。
现在有个周年庆宴会，宴会每邀请来一个职员都会增加一定的快乐指数 ri，但是呢，如果某个职员的直接上司来参加舞会了，那么这个职员就无论如何也不肯来参加舞会了。
所以，请你编程计算，邀请哪些职员可以使快乐指数最大，求最大的快乐指数。
输入格式
输入的第一行是一个整数 n。
第 2 到第 (n+1) 行，每行一个整数，第 (i+1) 行的整数表示 i 号职员的快乐指数 ri。
第 (n+2) 到第 2n 行，每行输入一对整数 l,k，代表 k 是 l 的直接上司。
输出格式
输出一行一个整数代表最大的快乐指数。
思路
一道树形dp
二选择：去 不去
代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,dp[100005][15],r[123456],root;
bool j[1234567];
vector<int> g[100005];
void dfs(int u){
int s1=0,s2=0;
for(int i=0;i<g[u].size();i++){
int v=g[u][i];
dfs(v);
s1+=max(dp[v][0],dp[v][1]);
s2+=dp[v][0];
}
dp[u][0]=s1;
dp[u][1]=s2+r[u];
}
signed main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>r[i];
for(int i=1;i<n;i++){
int t1,t2;
cin>>t1>>t2;
g[t2].push_back(t1);
j[t1]=true;
}
for(int i=1;i<=n;i++) if(!j[i]) root=i;
dfs(root);
cout<<max(dp[root][1],dp[root][0]);
return 0;
}
注意找一下树的根
