浅谈树形dp

系统管理员 2022-02-09 10:53 350阅读 0赞

### 总结： ###

这一周重点训练了树形dp。 对树形dp也有了一定的认识。  
先说一下总的观点吧。 树形dp一般无非就是求出子节点的状态从而进一步去更新根节点的状态。 一般的话，会用到dfs，从根节点开始，依次向下深搜。 将所有的叶子节点的状态值求出来就去更新根节点。 这是从叶子节点向根节点依次传值。 也有从根节点向叶子节点传值的题目。 这种题目，一般只要深搜一遍就可以得到正确的答案了。

还有一种题目，就是在树上做背包。题目会给你一个限制条件（例如：在这颗树上，只能选M个节点，问怎么选能使选的价值总和最大）。想这种题目就是一个树上背包问题。 对于这种题目的话，我觉得用左孩子，右兄弟的办法去做，是最容易理解的。 但是左孩子，右兄弟来解决的话，就要求知道输入数据的孩子和父亲的关系。然后如果不用左孩子右兄弟的做法的话。 那么我们可以这样理解（以01背包为例）：对于一颗子树而言，当我们要求他的根节点的值时，我们一定是知道他的叶子节点的状态值才能求。所以，我们可以把他的叶子节点的状态值理解为一个物品。这样的话，和01背包就没有什么差别了。  
对于树形dp的状态方程一般都是:  
dp\[i \]\[ \] = max\{dp\[v\]\[ \] \}  
表示第i颗子树的状态值是由他的子节点的子树的状态值通过转换得来的。第二维看情况。

当然，还有许多其他种类，在此就不一一列举。

题目链接：[http://poj.org/problem?id=2486][http_poj.org_problem_id_2486]  
这个题目要求最多走k步，问能摘到最多多少苹果。  
这是一个很典型的树上背包问题了。  
树上背包问题的话，无非就是一点在树上做背包。  
不过这个题，还有一个很有意思的地方，就是他一定回到起点吗？  
题目没做要求，所以他可以回到起点，也可以不回到起点。  
那么这就是两种情况了。 很明显，对于每颗子树都是有回到根节点和不回到根节点两种情况。

那么，状态转移方程就是：  
dp\[i\]\[k\]\[0\]=max(dp\[i\]\[k\]\[0\],dp\[v\]\[t-2\]\[0\]+dp\[i\]\[k-t\]\[0\];  
dp\[i\]\[k\]\[1\]=max(dp\[i\]\[k\]\[1\],dp\[v\]\[t-1\]\[1\]+dp\[i\]\[k-t\]\[0\],dp\[v\]\[t-2\]\[0\]+dp\[i\]\[k-t\]\[1\];  
这两种情况了。  
第一种表示在第i颗子树能走k步并回到根节点的情况。  
他在第i颗子树上最多走k步，那我们就要看他给每个叶节点分配1到k步所产生的影响，并取最优解。（如果他给这个叶节点分配了t（1<=t<=k）步，那么其他所有的叶子就只能走k-t步了,然后需要看他给这个叶子节点分配了t步，对整棵树产生了什么影响。继而枚举每个叶节点分配了t步对整棵树的影响，并取得最优解）。  
dp\[v\]\[t-2\]\[0\]表示：他给v这个叶子节点分配了t步并要回到根节点。  
这里有个问题就是为什么要t-2。我们可以想，他从i节点到v节点要花费一步，这一步不能算到v子树里面去，要减去。同样，他要回到i节点，又要花费一步，要减去。

第二个表示在第i颗子树下走k步不回到根节点的情况。  
他不回到根节点，那么我们要考虑他是在哪一个节点不回到根节点。  
,dp\[v\]\[t-1\]\[1\]+dp\[i\]\[k-t\]\[0\] 表示 他是在v这个叶节点不回到根节点。  
dp\[v\]\[t-2\]\[0\]+dp\[i\]\[k-t\]\[1\]表示，他是在不是v这个叶节点的其他叶节点不回到根节点。

代码：

#include"stdio.h"
    #include"string.h"
    #include"vector"
    #include"algorithm"
    using namespace std;
    
    int N,M;
    int weight[110],dp[110][220][2];
    vector<int>Q[110];
    void dfs(int root,int pre)
    {
        for(int i = 0; i < Q[root].size(); i ++)
        {
            int son = Q[root][i];
            if(son == pre)
                continue;
            dfs(son,root);//一直递归，直到叶子节点。
            for(int k = M; k >= 1; k --)
            {
                for(int t = 1; t <= k; t ++)
                {
                    dp[root][k][0] = max(dp[root][k][0],dp[son][t - 2][0] + dp[root][k - t][0]);
                    dp[root][k][1] = max(dp[root][k][1],dp[son][t - 1][1] + dp[root][k - t][0]);
                    dp[root][k][1] = max(dp[root][k][1],dp[son][t - 2][0] + dp[root][k - t][1]);
                }
            }
        }
    }
    int main()
    {
        while(~scanf("%d%d",&N,&M))
        {
            memset(dp,0,sizeof(dp));
            for(int i = 1; i <= N; i ++)
            {
                scanf("%d",&weight[i]);
                Q[i].clear();
                for(int j = 0; j <= M; j ++)
                {
                    dp[i][j][0] = dp[i][j][1] = weight[i];//初始化每一个值。
                }
            }
            for(int i = 1; i < N; i ++)
            {
                int a,b;
                scanf("%d%d",&a,&b);
                Q[a].push_back(b);
                Q[b].push_back(a);
            }
            dfs(1,0);
            printf("%d\n",max(dp[1][M][0],dp[1][M][1]));
        }
    }

题目链接：[http://poj.org/problem?id=3140][http_poj.org_problem_id_3140]  
这道题十分简单。但是要注意爆int，所以最大值的初始值一定要大。 我就是因为这个wa了。  
这道题，用一个dp\[i\]表示i这颗子树上有多少个节点。那么其他的节点个数不就是总节点个数减去dp\[i\]吗。 所以我们把每个子树的节点个数求出来并比较就可以了。

#include"stdio.h"
    #include"string.h"
    #include"vector"
    #include"math.h"
    #include"algorithm"
    using namespace std;
    typedef long long ll;
    
    ll N,M,sum,minx;
    ll dp[100010],weight[100010];
    vector<ll>Q[100010];
    ll abs1(ll sum)
    {
        if(sum < 0) sum = (ll)-1 * sum;
        return sum;
    }
    ll dfs(ll root,ll pre)
    {
        if(dp[root] != 0)    return dp[root];
        dp[root] = weight[root];
        for(int i = 0; i < Q[root].size(); i ++)
        {
            ll v = Q[root][i];
            if(v == pre) continue;
            dp[root] += dfs(v,root);
        }
        if(abs1(sum - dp[root] - dp[root]) < minx)
            minx = abs1(sum - dp[root] - dp[root]);
        return dp[root];
    }
    
    int main()
    {
        int cnt = 1;
        while(scanf("%lld%lld",&N,&M))
        {
            if(N + M == 0) break;
            sum = 0; minx = 1000001010000000;//一定要大点，不然爆
            for(int i = 1; i <= N; i ++)
            {
                scanf("%lld",&weight[i]);
                sum += weight[i];
                dp[i] = 0;
                Q[i].clear();
            }
            while(M --)
            {
                ll a,b; scanf("%lld%lld",&a,&b);
                Q[a].push_back(b);
                Q[b].push_back(a);
            }
            for(int i = 1; i <= N;i ++)
            {
                memset(dp,0,sizeof(0));
                dfs(i, 0);
            }
            printf("Case %d: %lld\n",cnt++,minx);
        }
    }

题目链接：[http://acm.hdu.edu.cn/showproblem.php?pid=1520][http_acm.hdu.edu.cn_showproblem.php_pid_1520]  
这个题意就是说如果选了他的上司就不能选他，反之，选了他，就不能选他的上司，问最多能选多少个人。  
我们可以看到，对于每一个人来说存在两种可能，1，选他，2，不选。  
所以我们可以定义一个dp\[n\]\[2\] 这样的一个dp数组来做这道题目。  
dp\[i\]\[0\]表示不选第i个节点，则他的子树最多能选多少个节点。  
dp\[i\]\[1\]表示选了dii个节点，则他的子树最多能选多少个节点。  
则状态转移方程就已经出来了。  
dp\[i\]\[0\] += max(dp\[v\]\[0\],dp\[v\]\[1\])  
dp\[i\]\[1\] += dp\[v\]\[0\];  
至于第一个方程为什么要用max，可以这么说，就是有可能存在i点不选 v点不选 选了v点的子节点，反而值会更大的情况。 这个情况很简单就能想到了，就不过多复述。

第二个方程就跟简单了。  
代码：

#include"stdio.h"
    #include"string.h"
    #include"vector"
    #include"algorithm"
    using namespace std;
    
    int dp[6010][2],weight[6010],n,in[6010];
    int vis[6010];
    vector<int>Q[6010];
    
    void dfs(int root)
    {
        dp[root][0] = 0 ;
        dp[root][1] = weight[root];
        for(int i = 0; i < Q[root].size(); i ++)
        {
            int v = Q[root][i];
            if(vis[v] == 0)
               {
                   dfs(v);
                   vis[v] = 1;
               }
            dp[root][0] += max(dp[v][0],dp[v][1]);
            dp[root][1] += dp[v][0];
        }
    }
    
    int main()
    {
        while(~scanf("%d",&n))
        {
            for(int i = 1; i <= n; i ++)
                {
                    scanf("%d",&weight[i]);
                    Q[i].clear();
                }
            memset(dp,0,sizeof(dp));
            memset(in,0,sizeof(in));
            memset(vis,0,sizeof(vis));
            while(1)
            {
                int a,b;
                scanf("%d%d",&a,&b);
                if(a == 0 && b == 0)
                    break;
                Q[b].push_back(a);
                in[a]++;
            }
            int root = 0;
            for(int i = 1; i<= n; i ++)
                if(in[i] == 0)
                {
                    root = i;
                    break;
                }
            dfs(root);
            printf("%d\n",max(dp[root][0],dp[root][1]));
        }
    }

题目链接：[http://poj.org/problem?id=1463][http_poj.org_problem_id_1463]  
这个题同上题。但是不知道为什么，我觉得这个题的题面有点问题，还是我自己理解的问题。 我自己造的一组数据，用我这个代码是过不了的。 但是这个代码是AC的。而且网上大部分也都是这个思路。

#include"stdio.h"
    #include"string.h"
    #include"vector"
    #include"algorithm"
    using namespace std;
    
    int n,dp[1510][2],in[1510];
    vector<int>Q[1510];
    
    void dfs(int root)
    {
        for(int i = 0; i < Q[root].size(); i ++)
        {
            int v = Q[root][i];
            dfs(v);
            dp[root][1] += min(dp[v][0],dp[v][1]);
            dp[root][0] += dp[v][1];
        }
    }
    
    int main()
    {
        while(~scanf("%d",&n))
        {
            memset(dp,0,sizeof(dp));
            memset(in,0,sizeof(in));
            for(int i = 1; i <= n; i ++) Q[i].clear();
            for(int i = 1; i <= n; i ++)
            {
                int id,cnt;
                scanf("%d",&id);
                id++;
                scanf(":(%d)",&cnt);
                while(cnt --)
                {
                    int a;
                    scanf("%d",&a);
                    a++;
                    Q[id].push_back(a);
                    in[a]++;
                }
                dp[i][0] = 0; dp[i][1] = 1;
            }
            int root = -1;
            for(int i = 1; i <= n; i ++)
                if(in[i] == 0)
                {
                    root = i; break;
                }
            dfs(root);
            printf("%d\n",min(dp[root][1],dp[root][0]));
        }
    }
    /*10
    0:(2) 1 2
    1:(1) 4
    2:(3) 7 8  9
    3:(0)
    4:(3) 3 5 6
    5:(0)
    6:(0)
    7:(0)
    8:(0)
    9:(0)*/
    //自己画图结果应该为2 但是输出3

望有大佬见到告知

题目连接：[http://acm.hdu.edu.cn/showproblem.php?pid=1561][http_acm.hdu.edu.cn_showproblem.php_pid_1561]  
这个题目的话，个人觉得用左儿子，右兄弟的方法做简单易懂的。其实也是一道树上背包问题。  
左儿子，右兄弟的意思是，定义一个儿子数组和兄弟数组。  
利用这两个数组来进行dp。  
dp\[i\]\[M\]= max(ans,dfs(son\[root\],k) + dfs(bro\[root\],M - 1 - k) + weight\[root\]);  
这个表示，在第i个结点的子树上能攻打M个城堡。但是注意，这M个城堡，可以分给他的儿子也可以分给他的兄弟。所以我们需要枚举k的大小，从而得到最优解。  
代码：

#include"stdio.h"
    #include"string.h"
    #include"algorithm"
    using namespace std;
    int N,M;
    int son[210],bro[210];
    int dp[210][210],weight[210];
    
    int dfs(int root,int M)
    {
        if(root == -1) return 0;
       // printf("root = %d\n",root);
        if(dp[root][M] != -1) return dp[root][M];
        int ans = dfs(bro[root],M);
        for(int k = 0; k <= M - 1; k ++)
        {
            ans = max(ans,dfs(son[root],k) + dfs(bro[root],M - 1 - k) + weight[root]);
        }
        return  dp[root][M] = ans;
    }
    int main()
    {
        while(~scanf("%d%d",&N,&M))
        {
            if(N == 0 && M == 0) break;
            memset(son,-1,sizeof(son));
            memset(bro,-1,sizeof(bro));
            memset(dp,-1,sizeof(dp));
            memset(weight,0,sizeof(weight));
            for(int i = 1; i <= N; i ++)
            {
                int a,b; scanf("%d%d",&a,&b);
                weight[i] = b;
                if(son[a] == -1)//这里是建立左儿子右兄弟的关键。
                    son[a] = i;
                else
                {
                    bro[i] = son[a];
                    son[a] = i;
                }
            }
            int maxx = dfs(son[0],M);
            /*for(int i = 0; i <= N; i ++)
            {
                for(int j = 0; j <= N; j ++)
                    printf("%d ",dp[i][j]);
                printf("\n");
            }*/
            printf("%d\n",maxx);
        }
    }

博主水平有限，许多地方也未叙述清楚。附上，学习树形dp的参考博客和有关视频，望对各位有所帮助。  
参考博客：[https://blog.csdn.net/dcx2001/article/details/78269908][https_blog.csdn.net_dcx2001_article_details_78269908]  
视频：[https://www.bilibili.com/video/av22695258?t=4289][https_www.bilibili.com_video_av22695258_t_4289]  
[https://www.bilibili.com/video/av12194537?t=2043][https_www.bilibili.com_video_av12194537_t_2043]

[http_poj.org_problem_id_2486]: http://poj.org/problem?id=2486
[http_poj.org_problem_id_3140]: http://poj.org/problem?id=3140
[http_acm.hdu.edu.cn_showproblem.php_pid_1520]: http://acm.hdu.edu.cn/showproblem.php?pid=1520
[http_poj.org_problem_id_1463]: http://poj.org/problem?id=1463
[http_acm.hdu.edu.cn_showproblem.php_pid_1561]: http://acm.hdu.edu.cn/showproblem.php?pid=1561
[https_blog.csdn.net_dcx2001_article_details_78269908]: https://blog.csdn.net/dcx2001/article/details/78269908
[https_www.bilibili.com_video_av22695258_t_4289]: https://www.bilibili.com/video/av22695258?t=4289
[https_www.bilibili.com_video_av12194537_t_2043]: https://www.bilibili.com/video/av12194537?t=2043