题解 P2996 【[USACO10NOV]拜访奶牛Visiting Cows】

· · 题解

树形DP

在学习树形动归之前，请先储备类似01背包，完全背包的知识；

顾名思义，树形动归就是在树上的动归，树形动归一般是依赖于dfs的，为什么呢，根据动归的后效性，父节点的状态一般都依赖子节点的状态以某种方式转移而来，而每一个父节点的孩子的数量不定，这就很难以寻常的递推式通过几个for解决掉，而大家可以想一下树这种东西它的遍历本身就依赖于dfs，可以说是比较暴力的打法了。

这里有一道很相似的题

没有上司的舞会 https://www.luogu.org/problemnew/show/P1352；

这是一道比较基础和经典的树形动归题；

那我们现在来分析一下这道题：

因为一个人不可能是他某个父节点的父节点，所以不可能出现环;如果一个点的父节点被访问，那么他的子节点就不会被访问，这样的话，就会出现

1.a（访问）->b（不访问）->c（访问）

2.a（访问）->b（不访问）->c(不访问）

这样我们就不能确定在b一定不去的情况下，是让c去而c的子节点不去而c的孙节点可以去的最终值大，还是c不去而c的子节点可以去的最终值大。这就是一个经典的......动归。

这里因为我们需要判断一个点的子节点是去了还是没去，所以可以加一维，以0为去了，1为没去。

那我们从哪个点开始呢，实际上从哪个点都可以，因为一个点的状态会以往上（父节点）和往下（子节点）的方式递归式传染，哪个点在上面哪个点在下面不重要。

下面给出代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;

int n,a,b,f[50003][2],used[50003];
vector <int> son[50003];

void dfs(int nx){
    used[nx]=1;
    for(int i=0;i<son[nx].size();i++){
        int v=son[nx][i];
        if(used[v]==1) continue;
        dfs(v);
        f[nx][1]+=f[v][0];
        f[nx][0]+=max(f[v][0],f[v][1]);
    }
}

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n-1;i++){
        scanf("%d%d",&a,&b);
        son[a].push_back(b);
        son[b].push_back(a);
        f[a][1]=1;//每一个点为一则被访问，f数组记录此状态下可以访问的总人数 
        f[b][1]=1;
    }
    dfs(1);
    printf("%d",max(f[1][1],f[1][0]));

    return 0;
}

后言

裸的树形动归一般是不会考的，树形dp可以与背包的思想相结合就是树形背包

下面给出两道树形背包的题

p2015 二叉苹果树 https://www.luogu.org/problemnew/show/P2015

p2014选课

https://www.luogu.org/problemnew/show/P2014