很烦啊，最近复习图论，贼艰难，很多题目基本多多少少都要用树形dp。而我专注于搞图论和数据结构，dp完全就是略知一二，逃避没有用，不会就去学，碰到困难就去面对。

树上dp其实跟普通的dp差不多，甚至会比普通的dp写起来简单，但是前提是要理解。

例题

洛谷P1352这个真的是典中典了，我看几乎所有的技术博客都会拿这个当作树形dp的入门题，那我也不例外。

题目分析

某大学有 \(n\) 个职员，编号为 \(1\ldots n\)。

他们之间有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。

现在有个周年庆宴会，宴会每邀请来一个职员都会增加一定的快乐指数 \(r_i\)，但是呢，如果某个职员的直接上司来参加舞会了，那么这个职员就无论如何也不肯来参加舞会了。

所以，请你编程计算，邀请哪些职员可以使快乐指数最大，求最大的快乐指数。

其实我觉得这个跟有依赖的背包题有异曲同工之妙，不通的是，他们不是依赖，而是互斥，选了一个人之后则不能选另一个人。而依赖背包则是选了一个则必须选另外一个，当然另外一个没有这个限制，否则两个物品直接合并一个物品啦。

这里很明显就是 \(n\) 个人 \(n-1\) 对关系，可以算做一棵树，但是这棵树是有向的，最顶级的那个上司就是树根了。这里我们肯定得先建一个有向图来保存这个关系，然后我们需要自底向上分析策略。对于每一个叶子节点，它们没有下级，对他们来说只有参加或者不参加，这里我们设 \(dp[i][0]\) 为第 \(i\) 个人不来参加的最优解，\(dp[i][1]\) 为第 \(i\) 个人来参加的最优解，注意这个最优解是对于它以及它的所有子孙节点的最优解。我们假设节点 \(i\) 有k个节点分别为 \(a_1,a_2\dots a_k\) ，那么可以写出如下状态转移方程。

\(dp[i][1] = \sum _{x=1} ^{k} dp[a_x][0]\)

\(dp[i][0] = \sum _{x=1} ^{k} \max(dp[a_x][0],dp[a_x][1])\)

这里很明显，对于本人不参加，那么自己的下属可参加可不参加，但是自己参加了自己的下属一定不能参加，而自己不参加选择下属参加还是不参加也是选取最优结果的，因此能得到上面的状态转移方程。然后就是最基本的树的操作了：建边，找根，dfs，状态转移，最后结果就是 \(\max(dp[root][1],dp[root][0])\)，所以这道题是真的入门题。

标程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<bits/stdc++.h>
using namespace std;
#define maxn 6500
struct eee{
    int to;
    int next;
}edge[maxn];
int root[maxn],degree[maxn],cnt,n,dp[maxn][2];
void add(int x,int y){
    degree[y]++;
    edge[++cnt].next=root[x];
    edge[cnt].to=y;
    root[x]=cnt;
    return ;
}
void dfs(int x){
    
    for(int i=root[x];i;i=edge[i].next){
        int v=edge[i].to;
        dfs(v);
        dp[x][0]+=max(dp[v][1],dp[v][0]);//状态转移方程
        dp[x][1]+=dp[v][0];
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>dp[i][1];
    }
    for(int i=1;i<n;i++){
        int x,y;
        cin>>x>>y;
        add(y,x);
    }
    for(int i=1;i<=n;i++){
        if(!degree[i]){//找根
            dfs(i);
            printf("%d\n",max(dp[i][1],dp[i][0]));
        }
    }
    return 0;
}