kkogoro

树形dp入门
树形dp入门Task1 树上最大独立集P1352没有上司的舞会题目大意:给你一棵树,树上每个节点有一个权值,当我们...
扫描右侧二维码阅读全文
09
2018/11

树形dp入门

树形dp入门

Task1 树上最大独立集

P1352没有上司的舞会

题目大意:

给你一棵树,树上每个节点有一个权值,

当我们选取一个节点后,它的儿子节点就不能选了,

我们要输出合理选择后,所得权值和的最大值。

分析:

显然这道题可以用记忆化搜索来解决,但是我们思考有没有更优美的做法。
我们把问题放到树上来看,每个节点有两种状态:选与不选,如果选,这个点的初始值就是它的权值,如果不选,它的初始值就是0。而我们要求的就是以$root$为根的(子)树的最终值。
根据题意,一个点的最终值取决与它的各个子节点所在子树的最终值。相似地,它的子树的最终值取决于这个子树的子树的最终值。思考如果我们有了一个节点的所有子节点所在子树的最终值,如何算出这个节点所在子树的最终值,转移方程:
​ $dp[fa,\space 0] = \sum_{son\in son_{fa}}max(dp[son,\space 0],\space dp[son, \space 1])$,
​ $dp[fa,\space 1] = Value_{fa}\space + \sum_{son\in son_{fa}}dp[son, 0]$
其中$1$ 表示选 $0$ 表示不选。
我们注意到原问题的规模正在缩小,并且每个阶段的转移过程是相同的,那么显然这是一个动态规划

考虑转移顺序:

每个节点的状态由它的子节点转移而来,而子节点需要从父亲节点进入,这个过程和$DFS$十分相似,我们显然可以用深度优先搜索来转移。

代码:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
const int MAXN = 6007;
int happiness[MAXN], dp[MAXN][2], indegree[MAXN];
std::vector<int>e[MAXN];
void DP(int u) {
    dp[u][0] = 0;
    dp[u][1] = happiness[u];
    for (std::vector<int>::iterator iter = e[u].begin(); iter != e[u].end(); ++iter) {
        int v = *iter;
        DP(v);
        dp[u][0] += std::max(dp[v][0], dp[v][1]);
        dp[u][1] += dp[v][0];
    }
}

int main() {
    int n, u, v;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &happiness[i]);
    }
    for (int i = 1; i < n; ++i) {   
        scanf("%d%d", &v, &u);
        e[u].push_back(v);
        ++indegree[v];
    }
    scanf("%d%d", &u, &v);
    int root = 1;
    for (; root <= n; ++root) {
        if (!indegree[root]) {
            DP(root); 
            break;
        }
    }
    std::cout << std::max(dp[root][0], dp[root][1]);
    return 0;
}

笔记:

树形DP设计一般以节点从深到浅(子树从小到大)的顺序作为DP的阶段。

DP的第一维通常是节点编号

除了使用递归,我们还可以使用BFS+for或者反向拓扑排序来进行状态转移

Task2 树形依赖背包

Vijos 1642 班长的任务 / 洛谷P2014 选课

这两道题的本质是相同的,这里就 Vijos 1642 班长的任务 展开讲解

题目大意:

给你一棵树,树上每个节点有一个整数权值,每个节点可以被选择(至多一次)

我们可以选取一个节点当且仅当它的父亲已经被选取,最多选择M个节点

我们要输出合理选择后,所得权值和的最大值。

分析:

考虑没有树形和必选父节点的限制,这其实是一个01背包
与树上最大独立集相反,这道题要求我们所选的点必须相邻且包含根节点,我们选择一个节点就必须选择它的父亲,这种子节点与父节点有一种依赖关系,因此称这种问题为树形依赖背包问题,因为有了依赖关系,这就不是一个01背包了,考虑设计状态和状态转移方程;

状态设计: $dp[u][j]$ 表示在节点 $u$ 为根的子树中选取 $j$ 个节点(必须合法,即满足依赖关系)的最大权值和(我定义的 $j$ 包含 $u$ 的计数,而有些题解在第一次处理时是按照不含 $u$ 而在最后把 $u$ 的计数添加进去的方法写的)

边界: 对于状态中的一个根 $u$ ,$dp[u][0] = 0$ 而 $dp[u][1] = val[u]$

状态转移方程: $dp[u][j] \space = \space max(dp[u][j], \space dp[u][j - k] \space + \space dp[v][k])$, $size[u]$ 是以 $u$ 为根的子树大小 , $v$ 是枚举 $u$ 的子节点 , $j$ 的枚举是从 $min(size[u], \space m)$ 到 $1$ (符合01背包的顺序), $k$ 是我们枚举从 $1$ 到 $j \space - \space 1$ 这实际上就跟分组背包的转移一样了:组就是对于子节点 $v$ 的各个 $dp$ 值构成的组,这是因为它们所代表的选择方案是不能同时存在于同一个最终决策中的,即相互冲突。

这样的时间复杂度是 $O(NM^{2})$

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>


const int MAXN = 1007;


struct Edge {
    int v;
    Edge *nextEdge;
} e[MAXN];
Edge *head[MAXN];
inline void insert(int u, int v) {
    static int cntEdge;
    Edge *it = &e[++cntEdge];
    it->v = v, it->nextEdge = head[u], head[u] = it;
    return;
}    


int dp[MAXN][MAXN], val[MAXN], size[MAXN];


void DP(int u, int m) {
    size[u] = 1, dp[u][0] = 0, dp[u][1] = val[u];


    for (Edge *it = head[u]; it != NULL; it = it->nextEdge) {
        int v = it->v;
        DP(v, m);
        size[u] += size[v];
    }


    for (Edge *it = head[u]; it != NULL; it = it->nextEdge) {
        int v = it->v;
        for (int w = std::min(size[u], m); w >= 1; --w) {
            for (int j = 1; j < w; ++j) {
                dp[u][w] = std::max(dp[u][w], dp[u][w - j] + dp[v][j]);
            }
        }
    }
    return;
}


int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    for (int u = 1; u <= n; ++u) {
        int s;
        scanf("%d%d", &val[u], &s);
        for (int j = 1; j <= s; ++j) {
            int v;
            scanf("%d", &v);
            insert(u, v);
        }
    }
    
    memset(dp, 0xCF, sizeof dp);
    DP(1, m);
    int ans = 0;
    for (int i = 0; i <= m; ++i) {
        ans = std::max(ans, dp[1][i]);
    }
    printf("%d", ans);
    return 0;
}

*转化为序列来优化

这种优化很妙,建议读者阅读论文《浅谈数据的合理组织》以透彻理解这个技巧

我们求出每个点的dfs序(先根序)

状态定义: 设 $dp[i][j]$ 表示在dfs序 $[i, n]$ 中选取 $j$ 个节点的最大权值(在这个区间内的节点意义下满足依赖关系)

状态转移方程: $dp[i][j] = max(dp[i + 1][j - 1] + val_{i}, dp[i + size_{pre_{i}}][j])$

$pre_{i}$ 指dfs序为 $i$ 的节点编号*(dfs序从 $1$ 开始),我们的 $i$ 从 $n$ 递推到 $1$ , 内层 $j$ 枚举选取的节点个数

如果我们选择 $pre[i]$ 号节点那么应该从它的子树(如果没有子树就由外面的节点的状态转移)转移过来,而它的第一个儿子dfs序为 $i + 1$ ,所以有了转移的第一项。如果不选 $pre[i]$ 号节点,那么我们不能从它的子树转移过来则跳过它的子树,即 $i + size[ pre[i] ]$

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>


const int MAXN = 1007;


struct Edge {
    int v;
    Edge *nextEdge;
}e[MAXN];
Edge *head[MAXN];
inline void insert(int u, int v) {
    static int cntEdge;
    Edge *it = &e[++cntEdge];
    it->v = v, it->nextEdge = head[u], head[u] = it;
    return;
}    


int pre[MAXN], size[MAXN], dp[MAXN][MAXN], val[MAXN];


void dfs(int u) {
    static int time_stamp;
    pre[++time_stamp] = u;
    size[u] = 1;
    for (Edge *it = head[u]; it != NULL; it = it->nextEdge) {
        int v = it->v;

        dfs(v);
        size[u] += size[v];
    }
    return;
}


int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    for (int u = 1; u <= n; ++u) {
        int s;
        scanf("%d%d", &val[u], &s);
        for (int j = 1; j <= s; ++j) {
            int v;
            scanf("%d", &v);
            insert(u, v);
        }
    }
    
    dfs(1);

    for (int i = n; i >= 1; --i) {
        for (int j = 1; j <= m; ++j) {
            dp[i][j] = std::max(dp[i + 1][j - 1] + val[ pre[i] ], dp[i + size[ pre[i] ] ][j]);
        }
    }
    printf("%d", dp[1][m]);
    return 0;
}
*对于洛谷的 选课 一题,由于直接建图得到的是森林,因此引入一个虚拟根节点,并且背包容量+1,dfs序的最大值+1

附上代码

#include <iostream>
#include <cstdio>
#include <algorithm>


const int MAXN = 307;


struct Edge {
    int v;
    Edge *nextEdge;
} e[MAXN << 1];
Edge *head[MAXN];
inline void insert(int u, int v) {
    static int cntEdge;
    Edge *it = &e[++cntEdge];
    it->v = v, it->nextEdge = head[u], head[u] = it;
    return;
}


int val[MAXN], pre[MAXN], size[MAXN], dp[MAXN][MAXN];


void dfs(int u) {
    static int time_stamp;
    pre[++time_stamp] = u;
    size[u] = 1;
    for (Edge *it = head[u]; it != NULL; it = it->nextEdge) {
        int v = it->v;
        dfs(v);
        size[u] += size[v];
    }
    return;
}


int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) {
        int fa;
        scanf("%d%d", &fa, &val[i]);
        insert(fa, i);
    }
    dfs(0);
    for (int i = n + 1; i >= 1; --i) {
        for (int j = 1; j <= m + 1; ++j) {
            dp[i][j] = std::max(dp[i + 1][j - 1] + val[ pre[i] ], dp[i + size[ pre[i] ]][j]);
        }
    }
    printf("%d\n", dp[1][m + 1]);
    return 0;
}

节点有体积和价值

方程改成即可(如果加虚拟节点注意虚拟节点的体积如果为0,那么背包容量不用改)

状态转移方程: $dp[i][j] = max(dp[i + 1][j - weight[ pre[i] ] + val_{i}, dp[i + size_{i}][j])$


Task3 求树的直径

直径:树中(边权和距离)最远的两个节点之间的距离被称为树的直径

连接这两个点的路径被称为树的最长链

我们设 $D[x]$ 为从节点 $x$ 出发能够到达它子树中的最远的节点的距离,设 $v_{1...k} $表示 $x$ 的子节点, $E(x, v)$ 表示这条边的边权,则有状态转移方程$D[x] = max(D[v] + E(x, v))$

用 $F[x]$ 表示经过 $x$ 的最长链长度(节点 $x$ 作为链的端点的LCA),

对于 $x$ 的孩子们,设存在两点 $v_{i}$ , $v_{j}$ , 则经过 $x$ 的最长链长度分为四个部分 $D[v_{i}]$ , $D[v_{j}]$ , $E(x, vi)$ , $E(x, vj)$ 。所以朴素的状态转移方程也十分显然

$ F[x] = max(D[v_{i}] + D[v_{j}] + E(x, v_{i}) + E(x, v_{j})) $

注意此处是使用孩子的 $D$ 值参与更新的

朴素方法一定是 设 $i < j$ ,然后双循环枚举 $i$ , $j$ ;

我们的 $F[x]$ 是一个最大的 $D[x]$ 和一个次大的 $D[x]$ 来更新的。

注意这里 $F$ 被分为两部分, $D[v_{i}] + E(x, v_{i})$  和 $D[v_{j}] + E(x, v_{j})$ ,这个表达式正是 $D[x]$ 的状态转移中的的表达式,并且每次更新 $D[x]$ 就是找到更长 $D$ 的过程,此时原来的 $D[x]$ 是次大值,新的 $D[x]$ 是最大值,从而优化到线性复杂度

//树的直径DP
void dp(int u) {
    vis[u] = true;
    for (Edge *it = head[u]; it != NULL; it = it->nextEdge) {
        int v = it->v;
        if (vis[v] == true) continue;
        
        dp(v);
        F[u] = max(F[u], D[u] + D[v] + it->w);
        D[u] = max(D[u], D[v] + it->w);
    }
}

Task4 求树的重心

树的重心:把这个节点删除后生成的各个树的大小的最大值最小
选择一个根节点dfs遍历。对于一个节点 $u$ 以每个孩子为根的子树的大小 $size[v]$ 和自己为根的子树外的点数 $n - size[u]$ 与目前全局最大值比较,更新答案

一棵树最多有两个重心,并且只有偶数节点数才会有两个重心并且两个重心相邻,把两棵树连接起来,新的重心在原来两棵树的重心的路径上,分出来的子树大小小于等于 $n/2$

int ans_pos, ans_size, size[MAXN];
void dfs(int u) {
    size[u] = 1;
    int temp_max = 0;
    for (Edge *it = head[u]; it != NULL; it = it->nextEdge) {
        int v = e[i].v;
        if (size[v] > 0) continue;
        
        dfs(v);
        size[u] += size[v];
        temp_max = max(temp_max, size[v]);
    }
    temp_max = std::max(temp_max, n - size[u]);
    if (temp_max > ans_size) {
        ans_size = temp_max;
        ans_pos = u;
    }
}

Task5 不定根问题(二次扫描法)

不定根问题在动态规划时整棵树没有一个确定的根(通常与最优根,选取根有关),暴力是枚举选取的节点进行n遍dp,一般处理这个问题用到二次扫描,第一次任意选取一个节点作为根求出一些信息(一般是每个点子树内到子树的信息,利用递归自底向上更新),第二次扫描从第一次的根出发,(推出逆向公式)自顶向下更新每个点子树外的信息。

树上最远点对距离

hdu2196

题目大意:

求出树上距离每个点距离最远的点的距离(权值和),树边上的权值为正整数

数据范围:

点数 $N\leq 10^{4}$

求解:

任意选取一个点作为根节点转化为有根树,到一个节点的最远点只有两种位置的情况:在它的子树里,在它的子树外面

如图,对于红色节点,我们要统计它子树内的最远点(可以通过dfs简单实现),还要考虑它父亲的其他儿子的子树,它父亲子树外面的节点。

状态定义: $dis[u][0]$ 表示节点 $u$ 的子树内距离 $u$ 最远节点到 $u$ 的距离, $dis[u][1]$ 表示节点 $u$ 子树内距离 $u$ 次远节点到 $u$ 的距离(非严格次远,跟最远距离相等的另一个距离也行)。 $maxC[u]$ 表示最后一次更新 $dis[u][0]$ 的 $u$ 的孩子。 $outDis[u]$ 表示 $u$ 子树外的节点到 $u$ 的最远距离

我们先用一次dfs求出每个点的子树内到它的最远距离,次远距离以及最后一次更新最远距离的儿子,然后用再一次dfs统计子树外的节点到它的最远距离,我们使用父亲节点更新孩子节点的状态,如果一个孩子不是更新它父亲节点最远距离的节点,那么它的子树外最远距离可以由 (它父亲的子树外最远距离 + 连接父亲与它的边权) 和 (它父亲子树内的最远距离 + 连接父亲与它的边权) 取最大值更新;

如果一个孩子是更新它父亲节点最远距离的节点,那么它的子树外最远距离可以由 (它父亲的子树外最远距离 + 连接父亲与它的边权) 和 (它父亲子树内的次远距离 + 连接父亲与它的边权) 取最大值更新;

状态转移方程: 分为两部分,直接看代码吧。。。

#include <iostream>
#include <cstdio>
#include <cstring>


const int MAXN = 10007;


struct Edge {
    int v, w;
    Edge *nextEdge;
} e[MAXN << 1];
Edge *head[MAXN];
int cntEdge;
inline void insert(int u, int v, int w) {
    Edge *it = &e[++cntEdge];
    it->v = v, it->w = w, it->nextEdge = head[u], head[u] = it;
    return;
}


int dis[MAXN][2], out_dis[MAXN], max_ch[MAXN], fa[MAXN];
void dfs1(int u) {
    for (Edge *it = head[u]; it != NULL; it = it->nextEdge) {
        int v = it->v;
        if (fa[u] == v) continue;
        fa[v] = u;
        dfs1(v);
        if (dis[v][0] + it->w >= dis[u][0]) {
            dis[u][1] = dis[u][0];
            dis[u][0] = dis[v][0] + it->w;
            max_ch[u] = v;
        }
        else {
            dis[u][1] = std::max(dis[u][1], dis[v][0] + it->w);
        }
    }
    return;
}
void DP(int u) {
    for (Edge *it = head[u]; it != NULL; it = it->nextEdge) {
        int v = it->v;
        if (fa[u] == v) continue;
        if (v == max_ch[u]) {
            out_dis[v] = std::max(dis[u][1], out_dis[u]) + it->w;
        }
        else {
            out_dis[v] = std::max(dis[u][0], out_dis[u]) + it->w;
        }

        DP(v);
    }
    return;
}


inline void init() {
    cntEdge = 0;
    memset(head, 0, sizeof head);
    memset(dis, 0, sizeof dis);
    memset(fa, 0, sizeof fa);
    memset(out_dis, 0, sizeof out_dis);
    memset(max_ch, 0, sizeof max_ch);
    return;
}


int main() {
    int n;
    while (~scanf("%d", &n)) {
        init();
        for (int u = 2; u <= n; ++u) {
            int v, w;
            scanf("%d%d", &v, &w);
            insert(u, v, w);
            insert(v, u, w);
        }

        dfs1(1);
        DP(1);

        for (int i = 1; i <= n; ++i) {
            printf("%d\n", std::max(dis[i][0], out_dis[i]));
        }
    }
    return 0;
}

POJ3585

题目大意:

给出一棵树,每条边有一个容量,选取一个节点作为源点(水量无限),那么以这个点为根节点的树的叶子节点为汇点,求选取哪个点时整棵树流量(从源点出发的水量)最大,输出最大值。

#include <iostream>
#include <cstdio>
#include <cstring>


const int MAXN = 200007;


struct Edge {
    int v, w;
    Edge *nextEdge;
} e[MAXN << 1];
Edge *head[MAXN];
int cntEdge, degree[MAXN];
inline void insert(int u, int v, int w) {
    Edge *it = &e[++cntEdge];
    it->v = v, it->w = w, it->nextEdge = head[u], head[u] = it;
    return;
}


int sub_flow[MAXN], tot_flow[MAXN];
void dfs(int u, int fa) {
    for (Edge *it = head[u]; it != NULL; it = it->nextEdge) {
        int v = it->v;
        if (v == fa) continue;
        dfs(v, u);
        if (degree[v] == 1) {
            sub_flow[u] += it->w;
        }
        else {
            sub_flow[u] += std::min(it->w, sub_flow[v]);
        }
    }
    return;
}
void DP(int u, int fa) {
    for (Edge *it = head[u]; it != NULL; it = it->nextEdge) {
        int v = it->v;
        if (v == fa) continue;
        if (degree[u] == 1) {
            tot_flow[v] = sub_flow[v] + it->w;
        }
        else {
            tot_flow[v] = sub_flow[v] + std::min(it->w, tot_flow[u] - std::min(it->w, sub_flow[v]));
        }
        DP(v, u);
    }
    return;
}


inline void init() {
    cntEdge = 0;
    memset(head, 0, sizeof head);
    memset(degree, 0, sizeof degree);
    memset(sub_flow, 0, sizeof sub_flow);
    memset(tot_flow, 0, sizeof tot_flow);
    return;
}



int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        init();
        int n;
        scanf("%d", &n);
        for (int i = 1; i < n; ++i) {
            int u, v, w;
            scanf("%d%d%d", &u, &v, &w);
            insert(u, v, w);
            insert(v, u, w);
            ++degree[u], ++degree[v];
        }
        dfs(1, -1);
        tot_flow[1] = sub_flow[1];
        DP(1, -1);
        int ans = 0;
        for (int i = 1; i <= n; ++i) {
            ans = std::max(tot_flow[i], ans);
        }
        printf("%d\n", ans);
    }
    return 0;
}

Task6 树上博弈

Last modification:November 15th, 2018 at 09:05 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment