时间限制: 1 Sec 内存限制: 128 MB 题目描述 Ural周立大学的校长正在筹备学校的80周年纪念聚会。由于学校的职员有不同的职务级别，可以构成一棵以校长为根的人事关系树。每个职员都有一个唯一的整数编号（范围在1到N之间），并且对应一个参加聚会所获得的欢乐度。为了使每个参加聚会者都感到欢乐，校长想设法使每个职员和他（她）的直接上司不会同时参加聚会。 你的任务是设计一份参加聚会者的名单，使总的欢乐度最高。 输入 输入的第一行是一个整数N，1<= N <= 6000 以下的N行是对应的N个职员的欢乐度（欢乐度是一个从-128到127之间的整数） 接着是学校的人事关系树，树的每一行格式如下： < L > < K > 表示第K个职员是第L个职员的直接上司。 输入以0 0表示结束 输出 输出参加聚会者获得的最大总欢乐度 样例输入 7 1 1 1 1 1 1 1 1 3 2 3 6 4 7 4 4 5 3 5 0 0 样例输出 5
思路：对于每个领导来说，他不去的快乐度为他旗下所有员工去/不去快乐度的最大值，他去的快乐度为他旗下不去的快乐度（领导去则其员工一定不去）加上其自身的快乐度，状态转移方程为：
dp[root][1]+=dp[g[root][i]][0]; dp[root][0]+=max(dp[g[root][i]][0],dp[g[root][i]][1]);其中i为root领导的某员工
题目代码：
#include<bits/stdc++.h> using namespace std; int n,w[6005],a,b; int book[6005],dp[6005][3]; vector <int> g[6005]; void dfs(int root) { //给dp[root][]初始值 dp[root][1]=w[root]; dp[root][0]=0; int len = g[root].size(); for(int i = 0;i < len; i++) { //遍历其每个子节点 dfs(g[root][i]); //如果领导去，这个人就不去 dp[root][1]+=dp[g[root][i]][0]; //如果领导不去，这个人可以去也可以不去 dp[root][0]+=max(dp[g[root][i]][0],dp[g[root][i]][1]); } } int main() { cin>>n; for(int i = 1; i <= n; i++) scanf("%d",&w[i]); while(cin>>a>>b)//b是a的上司 { if(!a&&!b)break; //将a变成b的员工 g[b].push_back(a); //a有上司，所以一定不是根节点 book[a]=1; } for(int i = 1; i <= n; i++) { if(!book[i])//i为根节点 { //从根节点开始深搜 dfs(i); //输出答案 cout<<max(dp[i][1],dp[i][0])<<endl; break; } } return 0; }