Anniversary party（树形DP）_综合

最近在做蓝桥杯的题目，刚遇到这种树形DP的问题，不知道如何下手，网上有很多类似的讲解，但是很多讲的都不够清楚，现在我对一道比较简单的树形D题目Anniversary party做一个讲解，顺便理清一下自己的思路。

题目描述：

某公司要举办一次晚会，但是为了使得晚会的气氛更加活跃，每个参加晚会的人都不希望在晚会中见到他的直接上司，现在已知每个人的活跃指数和上司关系（当然不可能存在环），求邀请哪些人（多少人）来能使得晚会的总活跃指数最大。

题意：

有n个人，接下来n行是n个人的价值，再接下来n行给出l，k说的是l的上司是k，这里注意l与k是不能同时出现的

输入

输出

思路：

用dp数据来记录价值，价值为活跃度

状态转移方程为：

DP[i][1]+=DP[j][0];//上司被选中，下属不选

DP[i][0]+=max{DP[j][0],DP[j][1]};//上司不被选中，下属可选可不选

从根节点r开始进行dfs，得到最后的结果为max{[DP[r][0],DP[r][1]}。

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;int father[6005],vis[6005],dp[6005][2],t;//father数组用于记录父节点，vis数组用于记录该节点是否已经被访问过，dp数组动态记录价值，t为人总数void dfs(int node)
{int i;vis[node] = 1;//因为从node节点开始访问，所以node节点要已被访问过for(i = 1;i<=t;i++)//从第一个人开始遍历{if(!vis[i] && father[i] == node)//如果该节点已经被访问过而且该节点作为父节点{dfs(i);dp[node][1]+=dp[i][0];//node去,则i必不能去dp[node][0]+=max(dp[i][0],dp[i][1]);//node不去，取i去或不去的最大值}}
}int main()
{int i,l,k,root;//i用于遍历每个节点，l是i上司，k用于记录上司，root为当前根节点while(~scanf("%d",&t)){for(i = 1;i<=t;i++)scanf("%d",&dp[i][1]);//输入每个人对应的价值root = 0;while(scanf("%d%d",&l,&k),l+k>0)//输入每个人对应的上司{father[l] = k;//记录上司root = k;}memset(vis,0,sizeof(vis));//开始所有节点都没有被访问过dfs(root);//从当前根节点开始进行dfsprintf("%d\n",max(dp[root][1],dp[root][0]));//输出动态规划数组填表后的最后值，即为要求的最大价值}return 0;
}



  
   ??