没有上司的舞会
P1352 没有上司的舞会 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
此题画出来是一种这样的结构（有一种“前向星存图”的方法，但这题没必要用）
同样可以采取dp的思考方式
dp[n][2] 数组代表每个人做出决策之后的快乐值，0是不去，1是去
1.初始化
dp[x][0]=0;
dp[x][1]=r[x];
2.状态转移方程
如果x是当前职工，y是他的下属，那么：
dp[x][0]+=max(dp[y][0],dp[y][1]); //上司没去，下属要么去，要么不去，那就取一个max
dp[x][1]+=dp[y][0];? ? ? ? //上司去了下属不去
那么，我们如何获取所有下属的每一种情况呢——树形结构——遍历+递归！
void dfs(int x){
//树形dp常常要用递归，自底向上
dp[x][0]=0; //不参加，带来的快乐值贡献为0
dp[x][1]=r[x]; //参加
for(int i=0;i<son[x].size();i++){
//遍历ta的所有下属
int y=son[x][i]; //y是当前遍历到的下属的编号
dfs(y);
dp[x][0]+=max(dp[y][0],dp[y][1]);
dp[x][1]+=dp[y][0];
}
} 在遍历中就更新了dp数组~~~
那么，把谁作为参数传进去呢？
显然应该传“树根”——树根就是没有上司的那一个人（而且题目中说了这是树，不会有图那种情况）
所以再额外设定一个v数组，来记录每一个员工有没有上司
当我们记忆化搜索了所有的情况，dp数组也都有了值，现在就要获取答案了
很简单，树根收集了所有子树的情况：
?? ?cout<<max(dp[root][0],dp[root][1])<<endl;
至此完成
完整代码：
#include<iostream>
#include<vector>
using namespace std;
#define MAXN 6005
int r[MAXN]; //快乐指数
int v[MAXN];
vector<int> son[MAXN]; //每个人都存一个自己的下属数组
int dp[MAXN][2]; //dp[i]代表第i个人，0不去，1去
void dfs(int x){
//树形dp常常要用递归，自底向上
dp[x][0]=0; //不参加，带来的快乐值贡献为0
dp[x][1]=r[x]; //参加
for(int i=0;i<son[x].size();i++){
//遍历ta的所有下属
int y=son[x][i]; //y是当前遍历到的下属的编号
dfs(y);
dp[x][0]+=max(dp[y][0],dp[y][1]);
dp[x][1]+=dp[y][0];
}
}
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++)
cin>>r[i];
for(int i=1;i<n;i++){
int x,y;
cin>>x>>y;
son[y].push_back(x);
v[x]=1; //代表ta有上司
}
int root;
for(int i=1;i<=n;i++){
if(!v[i]){
root=i;
break; //找到没有上司的那个人
}
}
dfs(root);
cout<<max(dp[root][0],dp[root][1])<<endl;
return 0;
}
