树上的动态规划

对于树上的动态规划问题，一般可以分为两类：树型结构的DP问题和树形背包。两种模型都存在树型的依赖关系，前者侧重相邻节点间的制约条件，后者则更像是一个有依赖关系的背包问题……

一 树型结构的DP问题

1 模型

给定$ n $个物品，且这些物品构成一个树形结构。
树上的父节点与子节点间存在一些制约，通常表现为父子节点无法同时被选择。同时，每件物品还有一个权值（点权）。

这就是树形结构的DP问题的基本模型。

树形结构的DP问题通常用来求解上述模型的 最大/最小 点权和。

「luogu P1352」没有上司的晚会

某大学有N个职员，编号为1~N。他们之间有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。现在有个周年庆宴会，宴会每邀请来一个职员都会增加一定的快乐指数Ri，但是呢，如果某个职员的上司来参加舞会了，那么这个职员就无论如何也不肯来参加舞会了。所以，请你编程计算，邀请哪些职员可以使快乐指数最大，求最大的快乐指数。

很明显，上司与职员的关系构成一棵树，树上的子节点与父节点无法同时被选择。

2 状态设计

定义$ f_{i,k} $为考虑以$ i $为根的子树，且节点$ i $的选择状态为$ k $时求的的解（$ k=1 $表示选择节点$ i $，$ k=0 $表示不选择节点$ i $）。

• 因为当前节点一旦选中，子节点则全部无法选择，故转移方程一：
  $$ f_{i,1} = \sum_{i,j \in E}f_{j,0} $$（$ E $为边集）

• 若当前节点不被选中，子节点则可选可不选，故转移方程二：
  $$ f_{i,0} = \sum_{i,j \in E}\max f_{j,0},f_{j,1}$$（$ E $为边集）

答案为$ \max f_{1,0},f_{1,1} $。

3 实现

因为状态的转移需要由叶向根转移，我们可以借助dfs实现状态的转移。

int dp(int cur)
{
    f[cur][1]=v[cur]; //预处理 
    
    for(int k=hd[cur]; k; k=E[k].nxt) //遍历边表
    {
        int to=E[k].to;
        
        dp(to);//求出子节点的两个状态 
        f[cur][0]+=max(f[to][0], f[to][1]);//判断子节点选和不选哪个更优 
        f[cur][1]+=f[to][0];//sigema
    }
    
    return max(f[cur][0], f[cur][1]);
}

---

二 树形背包问题

1 模型

给定$ n $个物品，子物品和主物品存在依赖关系，且这些关系满足树的性质，即所有物品构成一个树形结构。
每个节点有点权。令在其中选出$ m $个，且对于任意一棵子树，必须先选中父节点，才可以在该子树的所有节点中选择。

• 这就是树形背包问题的基本模型。

树形背包通常用来求解上述模型的 最大/最小 点权和。

「Luogu P2014」选课

在大学里每个学生，为了达到一定的学分，必须从很多课程里选择一些课程来学习，在课程里有些课程必须在某些课程之前学习，如高等数学总是在其它课程之前学习。现在有N门功课，每门课有个学分，每门课有一门或没有直接先修课（若课程a是课程b的先修课即只有学完了课程a，才能学习课程b）。一个学生要从这些课程里选择M门课程学习，问他能获得的最大学分是多少？

显然，先修课与后修课的关系满足树状结构。

2 状态设计

定义$ f_{i,s_i} $为选中节点 $ i $，且当前节点为根的树中选择$ s_i $个节点（不含根）的解。

设$sum_i$为子树$i$的总结点数。
对于节点$ i $，当固定了$s_i$的值时，它的$f$值可以分成两个部分：它的一棵子树的解（$f_{j,s_j}$）和其他子树的解之和（$ f_{i,s_i-s_j-1}$ )。因为$s_j$里面实际不包含节点$j$，所以最后还要$-1$。

那么转移方程：

$ f_{i,s_i} = \max f_{j,s_j}+f_{i,s_i-s_j-1} +c[j] | s_i\leqslant sum_i,s_j\leqslant sum_j,(i,j)\in E$（$c[j]$为节点权值，$E$为边集）

2-1 小问题：为什么一棵子树不会被重复累加？

我们考虑以背包的方式更新当前节点的解，则一棵子树在被累加之前不会累加在$ f_{i,s_i-s_j-1}$ 中。

3 实现

因为状态转移需要知道当前的$ s_i $，且需要从叶向根转移状态，所以我们依然用dfs来实现。

统计子树节点需要一遍dfs。但是考虑任意节点，我们都可以分段的转移状态。即我们可以边统计它的节点个数，边转移状态，因为状态的转移是不存在后效性的。

void dfs(int cur,int prv) //cur当前，prv父节点
{
    sum[cur]=1;

    for(int k=hd[cur]; k; k=E[k].nxt) //遍历边表
    {
        int to=E[k].to;

        dfs(to, cur); //递归处理

        sum[cur] += sum[to]; //累加节点数

        for(int j=min(m, sum[cur]); j; j--) //分配给当前树的节点数
            for(int k=min(j-1, sum[to]); k>=0; k--) //分配给子树的节点数
                f[cur][j] = max(f[cur][j], f[to][k]+f[cur][j-k-1]+c[to]); //这里要加上子节点的权值，因为f[to][k]不包含节点to的权值
    }
}

题中树形结构可能构成森林，故我们假设森林有一个总根$0$，调用dfs(0,0)即可解决。

因为状态定义中每个$f$不包含根，故新增总根对答案状态无影响。

答案为$f_{0,m} $