树形DP

e_thinker · 2020-05-20 18:42:41 · 个人记录

树形DP

树形DP是指在“树”这种数据结构上进行的DP:给出一棵树，要求以最少的代价（或取得最大利益）完成给定的操作。通常这类问题规模较大，枚举算法的效率低，无法胜任，贪心算法不能得到最优解，因此需要用动态规划。

在树上做DP显得非常合适，因为树本身有“子结构”性质（树和子树），具有递归性，符合DP的性质。相比线性DP，树形DP的状态转移方程更加直观。不过，由于“树”这种数据结构比较繁琐，逻辑上比较复杂，状态转移方程不好设计，常常属于比较难的题目。

树的操作一般需要利用递归和搜索，用户需要熟练地掌握这些基础知识。树的遍历一般是从根结点往子结点方向深入，用DFS编程会比较简单。

树形DP 入门

P1352 没有上司的舞会

样例的树形关系

当结点选1，2，5，6，7时有最大值5。

根据DP的解题思路，定义状态为：

状态转移方程有两种情况：

• 不选择当前结点，那么它的子结点可选可不选，取其中的最大值： dp[u][0] += max( dp[son][1],dp[son][1] )

• 选择当前结点，那么它的子结点不能选，dp[u][1] += dp[son][0]

程序分成3个部分：

• （1）建树。本题可以用STL 的vector生成链表，建立关系树
• （2）树的遍历。可以用DFS，从根结点开始进行记忆化搜索
• （3）DP

#include<bits/stdc++.h>
using namespace std;
const int N=6010;
int value[N],dp[N][2],fa[N],n;
vector<int> tree[N];
//深度搜索
void dfs(int u) {
    dp[u][0] =0;    //赋初值：不参加宴会
    dp[u][1] =value[u]; //赋初值： 参加宴会
    for(int i=0;i<tree[u].size();i++) {     //逐一处理这个父结点的每个子结点 
        int son = tree[u][i];   //获取子结点
        dfs(son);
        dp[u][0] += max(dp[son][0],dp[son][1]);     //父结点不选，子结点可选可不选 
        dp[u][1] += dp[son][0];     //父结点选，子结点不能选 
    } 
} 

int main() {
    int x,y;
    cin>>n;
    for(int i=1;i<=n;i++) {
        cin>>value[i];
        fa[i]=-1;   //初始化父结点都为-1 
    }   
    for(int i=1;i<n;i++) {
        cin>>x>>y;
        tree[y].push_back(x);   //用邻接表建树 
        fa[x] = y;      //父子关系 
    }   
    int t=1;
    while(fa[t] != -1) {    //查找树的根结点 
        t= fa[t];
    }
    dfs(t);     //从根结点开始，用DFS遍历整棵树 
    cout<<max(dp[t][0],dp[t][1]);
    return 0;
} 

复杂度：上述代码遍历每个结点，总复杂度是O(n)。

树形DP 进阶

HDU 2196 Computer（树形dp经典）

复杂度分析：如果求从一个特点结点出发的最长路径，可以从这个结点出发，做一次BFS，每次扩展邻居结点，并记录到这个邻居结点的最长距离，复杂度是O(n)。求所有n个结点的最长距离，需要对每个结点单独做一次BFS，总复杂度是O(n^2)。但是由于题目规模较大，N≤10, 000，算法的复杂度最多只能是O(n log_2 n) 。下面用DP求解：

以结点4为例，它的最长距离分两种情况讨论：

• （1）以4为顶点的子树（左边圈起的部分）距结点4的最远距离L_1 。 对结点4来说，它的L_1很容易求，只要从结点4出发对它的子树做一次DFS，记录最大深度，就能求得L_1。那么如何求得树上所有结点的L_1值？可以从根结点1开始DFS，遍历所有的结点，在DFS返回的过程中记录每个结点的最大深度，即这个结点的L_1值（在下面的程序中实际上计算了每个结点的两个距离。以结点4为例，这两个距离是以4为顶点的最长距离one，即L_1值； 以4为顶点的第2长距离two）。

• （2）剩下部分（右边圈起来部分）到结点4的最长距离L_2。L_2 = 父结点2的最长距离 + dis(2,4)， dis(2,4)是2和4之间的距离。求L_2的关键是求父结点2的最长距离，它又分两种情况：

• • 1.从结点2往上走的最长距离，图中路径是2-1-3。 这可以通过DFS不断更新结点来获得。
• • 2.结点2除了结点4以外的其他子树的最长距离X，图中路径是2-5-8-9。在上面第（1）步中已经求得了每个结点的最长距离one和次长距离two。如果结点4在父结点2的最长子树上，那么X=two + dis(2,4)；如果结点4不在父结点2的最长子树上，那么X=one + dis(2,4)。

综上所述，距离结点4最远距离是max\{L_1, L_2 \}。在程序中，用dfs1()实现功能（1）,用dfs2()实现功能（2）。

状态设计：结点i的子树到i的最长距离dp[i][0]以及次长距离dp[i][1]；从结点i往上走的最短距离dp[i][2] 。

#include<bits/stdc++.h>
using namespace std;
const int N=10010;
struct node{
    int id, cost;   //子结点的编号和权值 
};
vector<node> tree[N];   
int dp[N][3];
int n;
void init_read() {
    for(int i=1;i<=n;i++)   tree[i].clear();
    memset(dp,0,sizeof(dp));
    for(int i=2;i<=n;i++) {
        int x,y;
        cin>>x>>y;
        node tmp;
        tmp.cost =y;
        tmp.id = i;
        tree[x].push_back(tmp); //i 是x的子结点 
    }
}
void dfs1(int fa) {         //DFS 先处理子结点，再处理父结点 
    int one=0 , two=0;
    for(int i=0; i<tree[fa].size(); i++) {      //遍历结点fa的所有子结点 
        node child = tree[fa][i];
        dfs1(child.id);     // 递归子结点，直到最底层  
        int cost = dp[child.id][0] + child.cost ;
        if(cost >=one) {    // 用one记录从fa往下走的最长距离 
            two= one;       // 原来最长距离one 变成第2长，用two记录 
            one= cost;
        } 
        if(cost<one && cost>two)    two=cost;   //用two记录第2长的距离 
    }
    dp[fa][0] =one;
    dp[fa][1] =two;
}

void dfs2(int fa) {     //先处理父结点，再处理子结点 
    for(int i=0;i<tree[fa].size();i++) {
        node child= tree[fa][i];
        if(dp[child.id][0] + child.cost == dp[fa][0]) {
                // child 在最长距离的子树上 
            dp[child.id][2] = max(dp[fa][2],dp[fa][1])+child.cost;
        }
            // child 不在最长距离的子树上 
        else dp[child.id][2] = max(dp[fa][2],dp[fa][0])+child.cost;
        dfs2(child.id); 
    }
}
int main() {
    cin>>n;
    init_read();
    dfs1(1);
    dp[1][2]=0;
    dfs2(1);
    for(int i=1;i<=n;i++) {
        cout<<max(dp[i][0],dp[i][2])<<" ";
    }
    return 0;
}
/*
5
1 1
2 1
3 1
1 1
*/

SP1437 Longest path in a tree （树的直径模板题）