清北学堂noip2019-DP图论-Day2树形DP

Author： YorkWu
发布时间：April 30, 2019
1175 views
No comments
1015 words
Categories：集训 OI

清北学堂noip2019-DP图论-Day2树形DP

#### 简单入门题——没有上司的舞会

一棵树，每个点有权值，一个点和其儿子 / 父亲不能同时取，求解从树上选取点能获得的最大权值。 \- 树形 DP 中的覆盖问题，同时是一个子树转移问题（当前树的最优解由子树的最优解得到） 对于这类问题，我们应该维护每个子树的最优解 并关注子树到根的转移方式

*   $dp\[i\]\[0\]$ 表示我们不选择 $i$ 节点时子树的最大值 $dp\[i\]\[1\]$ 表示我们选择 $i$ 节点时子树的最大值 转移方程，对于每个节点 $i$ 的所有子节点 $dp\[i\]\[0\] += max(dp\[j\]\[0\], dp\[j\]\[1\])$ $dp\[i\]\[1\] += dp\[j\]\[0\]$
```cpp
    #include<bits/stdc++.h>
    using namespace std;
    int n,f[6009][2],value[6009],root;
    bool vis[6009];
    vector<int> son[6009];
    void dp(int u){
        f[u][0]=0;
        f[u][1]=value[u];
        for(int i=0;i<son[u].size();i++){
            int y=son[u][i];
            dp(y);
            f[u][0]+=max(f[y][0],f[y][1]);
            f[u][1]+=f[y][0];
        }
    }
    int main(){
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>value[i];
        }
        while(1){
            int x,y;
            cin>>x>>y;
            if(x==y&&x==0) break;
            vis[x]=1;
            son[y].push_back(x);
        }
        for(int i=1;i<=n;i++){
            if(vis[i]==0){
                root=i;
                break;
            }
        }
        dp(root);
        cout<<max(f[root][0],f[root][1]);
        return 0;
    }
    
```
* * *

#### Codeforce——767C Garland

给定一个树，树有点权 要求你把树的某些边删去，使得树变成三个部分 每个部分的点权值和都相等 ![题目](http://yueyangwu.cn/wp-content/uploads/2019/04/图片1-1.png "题目") \- 思路：可以想到，一旦能够找到一颗子树和为$w_总/3$就把它和它的父节点断开，即可。 - 原因：因为如果两颗子树的和各是总和的三分之一，那么它们一定不会有交集。

* * *

#### HDU 3586

给定一颗无向带权树，要切断所有叶子节点和根节点的联系，每次切断的费用不能超过上限 Limit，问在保证 总费用 <=m 的情况下最小的 Limit - 二分+树形DP - dp\[u\]表示u子树中上限为limit时符合条件的最小总费用。 那么可以这样设计转移：
```cpp
    if(dis(u,v)>limit){
        dp[u]+=dp[v];
    }
    else{
        dp[u]+=min(dp[u],dis(u,v));
    }
```

* * *

#### Luogu P2458——保安站岗

设计状态$dp\[i\]\[0/1/2\]$， - $dp\[i\]\[0\]$表示靠父节点的控制 - $dp\[i\]\[1\]$表示靠自己的控制 - $dp\[i\]\[2\]$表示靠子节点的控制 这样即可推得状态转移方程： - $dp\[u\]\[0\]=\\sum min(dp\[v\]\[1\],dp\[v\]\[2\])$ - $dp\[u\]\[1\]=\\sum min(dp\[v\]\[0\],dp\[v\]\[1\],dp\[v\]\[2\])+val\[u\]$ - $dp\[u\]\[2\]=\\sum min(dp\[v\]\[1\],dp\[v\]\[2\])+某一个dp\[v\]\[2\]$(这个比较麻烦。。。)
```cpp
    #include<bits/stdc++.h>
    using namespace std;
    
    vector<int> son[1509];
    int n,v[1509],dp[1509][3];
    
    void f(int x,int fa){
        dp[x][0]=dp[x][1]=0;
        for(int i=0;i<son[x].size();i++){
            int y=son[x][i];
            if(y==fa) continue;
            f(y,x);
            dp[x][0]+=min(dp[y][1],dp[y][2]);
            dp[x][1]+=min(min(dp[y][0],dp[y][1]),dp[y][2]);
        }
        dp[x][1]+=v[x];dp[x][2]=0x3f3f3f3f;
        for(int i=0;i<son[x].size();i++){
            int y=son[x][i];
            if(y==fa) continue;
            dp[x][2]=min(dp[x][2],dp[x][0]-min(dp[y][1],dp[y][2])+dp[y][1]);
        }
    }
    
    int main(){
        cin>>n;
        for(int i=1;i<=n;i++){
            int x,m;
            cin>>x;
            cin>>v[x];
            cin>>m;
            for(int i=1;i<=m;i++){
                int y;
                cin>>y;
                son[x].push_back(y);
                son[y].push_back(x);
            }
        }
        f(1,-1);
        cout<<min(dp[1][1],dp[1][2]);
        return 0;
    }
```

* * *

#### 树上dp的链问题

有一类树上 DP 的问题，求的是树上的满足条件的“最优链” 经典问题：HDU 2196 给定一棵有边权的树，输出树中与其距离最远的点的距离值 - 显然，从一个节点x出发到达的点只有两种情况： 1. 在x的子树中。 2. 在x的子树外。

*   显然第一种十分好维护，令 f\[i\] 表示以 i 为起点的，到 i 的子树内距离最远是多少 则 $f\[i\] = max(f\[j\] + dist(i,j))$ 那么第二种如何维护？我们令 $g\[i\]$ 表示 i 为起点到 i 的子树外距离最远是多少 第二种情况需要再做一次分类 一类是经过它的父亲，到父亲外，即 $g\[i\]$ <- $g\[fa\[i\]\]$ 另一类是经过它的父亲，到了它的兄弟子树中

Last modification：March 14, 2020