Acwing算法进阶指南学习dp专题：树形dp

• 一般树形dp会给定一个有$n$个节点的树，通常是无根树。

• 然后选任意节点为根节点，从而定义每个结点的深度和每棵子树的根。

• 一般而言：以节点从深到浅（子树从小到大）的顺序作为dp的阶段；dp状态表示中，第一维通常是节点的编号（代表以该节点为根的子树。）大多数时候，采用递归的方式实现树形dp。
• 对于每个节点$x$，先递归在他的每个子节点上进行dp，回溯时，从子节点向节点$x$进行转移。

例题1：acwing285：没有上司的舞会

题意

• 一家公司有n个员工，编号为1~n。
• 他们的关系就像一棵以校长为根的数，父节点就是子节点的直接上司。
• 每个员工都有一个快乐指数。
• 现在要开一个周年庆典，没有员工愿意和直接上司参加舞会，问怎样安排能让快乐值最大，求最大值。
• 数据范围：$N\leq6000$

思路

• 对于每个人只有选和不选两种可能。
• 于是可以设计：$f(x,0/1)$表示选$x$或者不选$x$。
• 选了x则他的儿子不能选，不选x那他的儿子选或者不选都可以，那么就挑个最大的子树方案的值。
• 那么$f(x,0)+=max(f(son,0),f(son,1)),f(x,1)+=f(y,0)$。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 6e3 +10;
int h[maxn], f[maxn][3], n;
bool v[maxn];

int head[maxn], nex[maxn<<1], ver[maxn<<1], tot;
inline void add_edge(int x, int y){
    ver[++tot] = y; nex[tot] = head[x]; head[x] = tot;
}

void dfs(int x)
{
    f[x][0] = 0;
    f[x][1] = h[x];
    for(int i = head[x]; i; i = nex[i])
    {
        int y = ver[i]; dfs(y);
        f[x][0] += max(f[y][0], f[y][1]);
        f[x][1] += f[y][0];
    }
}

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) 
        scanf("%d", &h[i]);
    for(int i = 1, x, y; i++ <= n-1; )
    {
        scanf("%d%d", &x, &y);
        v[x] = 1; //x有父亲
        add_edge(y, x);
    } int rt;
    for(int i = 1; i <= n; i++)
    {
        if(!v[i]) {
            rt = i;
            break;
        }
    } dfs(rt);
    cout << max(f[rt][0], f[rt][1]) << endl;
    return 0;
}

例题2：acwing286：选课

题意描述

• 一个学校开设了N门课，每个学生可选课程的数量M是给定的。
• 学生选了M门课并考完就能拿到相应的学分。
• 有的课可以直接选，有的课得修完先修课才能选。
• 每门课直接选修课最多只有一门，两门课可能存在相同的先修课。
• 求选课方案使学分最高。
• 数据范围：$N\leq 300$。

思路

• 每门课都有先修课，那么可以想成一门课是他的先修课的儿子。
• 那一门课和他的后选课就可以构成一棵树。
• 然而有可能有很多课没有先修课，也就是由很多个根节点，那么这就是个森林。
• 为了方便起见，设立0号节点为虚节点，作为没有先修课的课的先修课。
• 设计转移方程$f(x,t)$表示在$x$及其子树中选$t$门课能得到的最大学分。
• 那么有$f(x,t)=\max(f(y,c))+sorce$。
• 这其实就是一个树上分组背包的模型。
• 稍作一下解释吧， 假设说$1$号节点是$2$号节点的父节点，那么对于$2$节点及其子树构成一组物品，对于$2$号节点有许多种体积的子背包，对于$1$号节点而言，他只能从这许多种体积的子背包中选一个加入自己的背包中，而$1$号节点有可能有许多个子节点，所以其实是树上分组背包。
• 因为我们必须要选根节点，所以我们m++，并从0号节点开始dfs。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 300 + 10;
int n, m, h[maxn];
int f[maxn][maxn];
int head[maxn], ver[maxn<<1], nex[maxn<<1], tot;
inline void add_edge(int x, int y){
    ver[++tot] = y; nex[tot] = head[x]; head[x] = tot;
}

void dfs(int x)
{
    for(int i = head[x]; i; i = nex[i])
    {
        int y = ver[i]; dfs(y);
        for(int j = m-1; j >= 0; j--)
        {
            //选择一个子节点体积为k的子背包
            for(int k = 0; k <= j; k++)
                f[x][j] = max(f[x][j], f[x][j-k] +f[y][k]);
        }
    }
    //本身要选修x
    if(x != 0)
    for(int i = m; i > 0; i--)
        f[x][i] = f[x][i-1] + h[x];
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1, x, y; i <= n-1; i++)
    {
        scanf("%d%d", &x, &y);
        add_edge(x, i); h[i] = y;
    } dfs(0);
    cout << f[0][m] << endl;
    return 0;
}

例题3：acw287：积蓄程度（换根+二次扫描）

题意描述

• 给定一颗树，每条边都有一个水容量，连接$x,y$的河道水容量记为$c(x,y)$。
• 河道中单位时间流过的水量不能超过河道的容量。
• 有一个点是水源的发源地，称为源点。
• 除了源点外，叶子节点为入海口，可以吸收无限的水容量，称为汇点。
• 也就是说水系的水从原点出发，沿着河道，最终流向汇点。
• 整个水系稳定时，水系的水都以单位时间固定的水量流向固定的方向。
• 除了源点和汇点之外，其余各点不存储水，也就是流入该点的水量之和等于流出该点的水量之和。
• 整个水系的流量定义为源点单位时间发出的水量。
• 问哪个点作为源点时，流量最大，求出这个流量。
• 数据范围：$n\leq 2*10^5$.

思路

• 换根。
• 其实这题有点不太像dp，因为他没有太多决策，（选或不选），只要确定了某个点为根然后算流量就行。但是要枚举每个根节点去求，复杂度就会到$O(n^2)$。
• 根据acwing站主yxc的讲解，换根法用这两个思路：
• 1：自下而上递推
• 2：自上而下递推
• 第一次扫描时：任选一个点为根，之后执行一次树形dp，也就是自底向上的状态转移。
• 第二次扫描时：从刚才的点出发，对整个书再进行一次自顶向下的推导，计算出换根之后的解。
• 设$d(x)$表示从$x$出发流向其子树的总流量。
• 那么对于$d(x)$我们就可以做第一次扫描，设$y$为$x$的子节点，那么有：
• 如果$y$是叶子节点，那么$d(x)+=c(x,y)$。
• 如果$y$不是叶子节点，那么有$d(x)+=min(d(y),c(x,y))$。
• 之后我们进行第二次的扫描。
• 设$f(x)$表示将$x$作为源点，流向整个水系的流量是多少。

• 那么显然有$f(root)=d(root)$。

• 假设$f(x)$已被正确求出，那么对于他的子节点$y$来说，有：

• 1：从$y$流向$y$的子树的流量，也就是$d(y)$。
• 2：从y沿着$y->x$的河道流向别的水系的其他部分的流量。
• 因为把$x$作为源点，流向$y$的流量就是$min(d(y),c(x,y))$。所以从$x$流向别的水系的流量就是$f(x)-min(d(y),c(x,y))$。
• 那么当$y$为源点的时候就有：
• $f(y)=d(y)+min\{f(x)-min\{d(y),c(x,y)\},c(x,y)\}$，$deg(x)>1$。
• $f(y)=d(y)+c(x,y)$，$deg(x)==1$.

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
int n, T;

int head[maxn], nex[maxn<<1], ver[maxn<<1], edge[maxn<<1], tot;
inline void add_edge(int x, int y, int z){
    ver[++tot] = y; edge[tot] = z;
    nex[tot] = head[x]; head[x] = tot;
}

int d[maxn], f[maxn], deg[maxn];

void dfs_d(int x, int fa)
{
    for(int i = head[x]; i; i = nex[i])
    {
        int y = ver[i], z = edge[i];
        if(y == fa) continue;
        dfs_d(y, x);
        if(deg[y] == 1) d[x] += z; //如果是叶子节点
        else d[x] += min(d[y], z);
    }
}

void dfs_f(int x, int fa)
{
    for(int i = head[x]; i; i = nex[i])     
    {
        int y = ver[i], z = edge[i];
        if(y == fa) continue;
        if(deg[x] == 1) f[y] = d[y] + z;
        else f[y] = d[y] + min(f[x]-min(d[y],z), z);
        dfs_f(y, x);
    }
}

void solve()
{
    scanf("%d", &n); tot = 0;
    for(int i = 1; i <= n; i++) 
        head[i] = deg[i] = d[i] = f[i] = 0;

    for(int i = 1, x, y, z; i <= n-1; i++)
    {
        scanf("%d%d%d", &x, &y, &z);
        add_edge(x, y, z); add_edge(y, x, z);
        deg[x]++, deg[y]++;
    }

    dfs_d(1, -1); f[1] = d[1]; dfs_f(1, -1);
    int ans = 0;
    for(int i = 1; i <= n; i++)
        ans = max(ans, f[i]);
    cout << ans <<endl;
}

int main()
{
    scanf("%d", &T);
    while(T--) solve();
    return 0;
}