DP专题7 | 没有上司的舞会 洛谷1352（树形DP）
DP专题7 | 没有上司的舞会 洛谷1352（树形DP）
高能预警：这是一篇超过5分钟的学习文章，暑假了可以多学会
本篇继续咱们的DP专题，树形DP入门。动态规划每一个类型的DP都是深坑，期望童鞋们自己在这个系列的基础上多花时间进行拓展，学习愉快~
在讨论树形DP之前，我想介绍一个比较有名的学习技巧——费曼技巧，因为个人觉得可以尝试着用在咱们的算法理解上。费曼这个人本身是一个很有意思的人，做科研和教育都非常厉害，另外后人还根据他的个人经历拍了一部爱情片，是不是跨越有点大，好了，先说费曼定理。
2012年，加拿大人斯科特.H.杨（Scott H Young）用一年的时间自学完成了MIT公开课上正常情况下需要四年才能修完的计算机科学的33门课程，并最终通过了所有考试。在分享其学习方法的时候，他提到了费曼技巧，从此，费曼技巧进入了公众视野。
那么，费曼技巧到底是什么呢？
在费曼的自传里，他提到曾纠结于某篇艰深的研究论文。他的办法是，仔细审阅这篇论文的辅助材料（supporting material），直到他掌握了相关的知识基础、足以理解其中的艰深想法为止。
费曼技巧，也可以称为四步学习法：
第一步 选择一个你想要理解的概念第二步 设想一种场景，你正要向别人传授这个概念第三步 如果你感觉卡壳了, 就回顾一下学习资料第四步 为了让你的讲解通俗易懂，简化语言表达
最终的目的, 是用你自己的语言, 而不是学习资料中的语言来解释概念。
先看到这里，下周会专门发一篇费曼技巧的文章。接着来看树形DP题目。
现学现用，思考一下树形DP的费曼解释
假设你要对一个是7岁小学1年级学生讲解，要怎样解释树形DP呢？
首先假设这个小学生已经了解了DP（1年级能理解DP也是厉害了），那么可以说：
树形DP就是基于树形搜索进行状态转移的DP。
好吧，还是很有难度的，有兴趣的童鞋可以留言说出你的想法
。
因为树形天生具有递归的性质，树形DP一般都是通过深度优先搜索进行迭代，从叶子节点回溯到根节点的过程。
你可以想象自己在一棵倒挂树的叶子节点上，一点点往根部爬。之前线性DP我们都是从f[0]这样的位置一点点往f[n]这样递推，树形DP是换了一种方式，从线性数组到树形。
题目描述
某大学有N个职员，编号为1~N。他们之间有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。现在有个周年庆宴会，宴会每邀请来一个职员都会增加一定的快乐指数Ri，但是呢，如果某个职员的上司来参加舞会了，那么这个职员就无论如何也不肯来参加舞会了。所以，请你编程计算，邀请哪些职员可以使快乐指数最大，求最大的快乐指数。
输入输出格式
输入格式：
第一行一个整数N。(1<=N<=6000)
接下来N行，第i+1行表示i号职员的快乐指数Ri。(-128<=Ri<=127)
接下来N-1行，每行输入一对整数L,K。表示K是L的直接上司。
最后一行输入0 0
输出格式：
输出最大的快乐指数。
本题是树形DP的经典入门题目，因为理解起来没那么复杂，转移方程如下图所示：
只用考虑上司去和不去2中状态，进行状态转移。
源代码：G++编译
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <bitset>
#include <iostream>
#include <set>
#include <string>
#include <vector>
#include <string.h>
using namespace std;
#define N 6100
int h[N];
int v[N];
vector<int> children[N];
int dp[N][2];
void dfs(int x)
{
// 对于叶子节点来说
// 不去为0分
dp[x][0] = 0;
// 去的话初始化为自己的欢乐指数
dp[x][1] = h[x];
for(int i=0; i<children[x].size(); ++i){
int y = children[x][i];
// 先递归计算孩子的欢乐指数
dfs(y);
// 加上孩子的欢乐指数
// 上司不去，孩子有可能去
dp[x][0] += max(dp[y][0], dp[y][1]);
// 上司去，孩子不去
dp[x][1] += dp[y][0];
}
}
int main() {
#ifdef __MSYS__
freopen("test.txt", "r", stdin);
#endif
int n;
scanf("%d", &n);
// 注意下标从1开始，因为题目都是用下标来指定位置的
for(int i=1; i<=n; ++i){
scanf("%d", &h[i]);
}
for(int i=1; ; ++i){
int c, p;
scanf("%d%d", &c, &p);
if(!c && !p)break;
// 用于判断是否为根节点，只有根节点没有parent
v[c] = 1;
// 用二维数组记录父子关系
children[p].push_back(c);
}
int root;
for(int i=1; i<=n; ++i){
if(!v[i]){
root = i;
break;
}
}
// 开始树形递归搜索（线性DP都是迭代搜索）
dfs(root);
printf("%d\n", max(dp[root][0], dp[root][1]));
return 0;
}