• 树形DP 复习笔记

    文章目录

    引入

    DP是OI中非常常用的算法，DP通常是以循环的形式呈现，前面的状态推后面的状态。但有些需要以递归形式呈现，借助搜索或者数据结构，就比如这次学习的树形DP。

    算法

    DP很少有固定的模板，在这次的学习中我们将更多地结合题目分析。

    树形DP通常是用子结点更新父节点，有少数情况会用父结点更新子结点，所以状态的第一维通常是结点编号，若有第二位通常是子树权值。

    一维树形DP

    [POI2008] STA-Station

    给定一个 n ( n ≤ 1 0 6 ) n (n\le 10^6) n(n≤106)个点的树，请求出一个结点，使得以这个结点为根时，所有结点的深度之和最大。

    我们令 s i z e s u sizes_u sizesu​为 1 1 1为根时 u u u子树点数， s u s_u su​为其子树深度和， r e s u res_u resu​为 u u u为根的答案（即 r e s 1 = s 1 res_1=s_1 res1​=s1​）。

    考虑先dfs一遍求出 s i z e s sizes sizes和 s s s，对于 v v v和其父结点 u u u，因为有了 u u u， v v v子树所有点深度会加 1 1 1，所以 s u = ∑ v s v + s i z e s v s_u=\sum_v{s_v+sizes_v} su​=∑v​sv​+sizesv​（子结点更新父结点）。现在需要考虑的是如何用 r e s 1 res_1 res1​推出 r e s 2 → n res_{2 \to n} res2→n​，我们来看下样例。

    以 1 1 1号点为根时：
    在这里插入图片描述
    以 4 4 4号点为根时：
    在这里插入图片描述

    发现了吗？ 4 4 4及其的子节点的深度全都减了 1 1 1，其它结点深度都加了 1 1 1。

    总结一下， u u u为根的树，变成其儿子 v v v为根的树，会获得 s i z e s v sizes_v sizesv​的收益和 n − s i z e s v n-sizes_v n−sizesv​的代价，即 r e s v = r e s u + n − 2 × s i z e s v res_v=res_u+n-2\times sizes_v resv​=resu​+n−2×sizesv​，这里我们在第二次dfs中求出，最终取max即可。（**tips:**对于本题，不开long long会WA两个点）。

    #include 
using namespace std;
typedef long long ll;
const int N = 1e6 + 5;
struct edge {
    int v, nxt;
} e[N << 1];
int head[N], k;
inline void add(int u, int v) {
    e[++k] = {v, head[u]}, head[u] = k;
}
int n, sizes[N];
ll s[N], res[N];
void dfs1(int u, int fa) {
    sizes[u] = 1, s[u] = 0;
    for (int i = head[u]; i; i = e[i].nxt) {
        int v = e[i].v;
        if (v != fa) {
            dfs1(v, u);
            sizes[u] += sizes[v], s[u] += s[v] + sizes[v];
        }
    }
}
void dfs2(int u, int fa) {
    for (int i = head[u]; i; i = e[i].nxt) {
        int v = e[i].v;
        if (v != fa) {
            res[v] = res[u] + n - 2 * sizes[v];
            dfs2(v, u);
        }
    }
}
int main() {
    ios :: sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n;
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        add(u, v), add(v, u);
    }
    dfs1(1, -1);
    res[1] = s[1];
    dfs2(1, -1);
    ll maxn = 0;
    int maxid;
    for (int i = 1; i <= n; ++i) {
        if (res[i] > maxn) {
            maxn = res[i], maxid = i;
        }
        maxn = max(maxn, res[i]);
    }
    cout << maxid << '\n';
    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55

    树上01背包

    给定 n n n个结点的以 1 1 1号点为根的树，初始所有树边都未解锁，解锁一条边需要一定能量，每个点均有 k k k点能量用来解锁和子结点之间的边，求最终最多多少点能与 1 1 1号点连通。

    为什么要叫背包呢？要选择的物品是什么呢？我们从头开始分析。

    最终要和 1 1 1号点连通，那我们就从 1 1 1号点开始搜索。树是一个神奇的结构，若此子树根与其父未连通，无论子树内如何操作也是无用的，所以我们考虑对每个点 u u u考虑其子树中最多能有多少个点与其连通，对于其子结点 v v v，如果解锁了 u u u和 v v v之间这条边，就相当于解锁了这个子树，再递归求解即可。

    看到这里大家应该发现了，因为每个子树独立，对于结点 u u u，我们可以将其所有子节点 v v v看成物品，花费是解锁 u u u和 v v v之间连边所需能量，价值就是子树 v v v的答案。

    我们定义 f u f_u fu​为子树 u u u的答案，状态转移和传统01背包相同。

    #include 
using namespace std;
const int N = 1e5 + 5;
struct edge {
	int v, w, nxt;
} e[N << 1];
int head[N], cnt;
void add(int u, int v, int w) {
	e[++cnt] = {v, w, head[u]}, head[u] = cnt;
}
int n, k, f[N], dp[N];
void dfs(int u, int fa) {
	for (int i = head[u]; i; i = e[i].nxt) {
		int v = e[i].v;
		if (v != fa) {
			dfs(v, u);
		}
	}
	memset(dp, 0, sizeof dp);
	for (int i = head[u]; i; i = e[i].nxt) {
		int v = e[i].v, cost = e[i].w, val = f[v];
		if (v != fa) {
			for (int j = k; j >= cost; --j) {
				dp[j] = max(dp[j], dp[j - cost] + val);
			}
		}
	}
	f[u] = dp[k] + 1;
}
int main() {
	ios :: sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> k;
	while (--n) {
		int u, v, w;
		cin >> u >> v >> w;
		add(u, v, w), add(v, u, w);
	}
	dfs(1, -1);
	cout << f[1] << '\n';
	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42

    树上多重背包

    和树上01背包问题基本相同，只是将每个点单独能量改为所有点共 k k k点能量。

    有童鞋会问，只是改了下能量的分配，物品数没有改变，怎么就变成多重了呢？——我们可以分配给每个点不同数量的能量，得到的价值也不同，同一种物品分配不同能量就相当于多重背包中的物品个数不同，可以用相同方式处理。

    这样状态定义就容易了，设 f u , i f_u,_i fu​,i​为给子树 x x x分配 i i i个能量的答案。

    #include 
using namespace std;
const int N = 1e4 + 5, K = 1e3 + 5;
struct edge {
	int v, w, nxt;
} e[N << 1];
int head[N], cnt;
inline void add(int u, int v, int w) {
	e[++cnt] = {v, w, head[u]}, head[u] = cnt;
}
int n, k, f[N][K];
void dfs(int u, int fa) {
	for (int i = head[u]; i; i = e[i].nxt) {
		int v = e[i].v;
		if (v != fa) {
			dfs(v, u);
		}
	}
	for (int i = head[u]; i; i = e[i].nxt) {	// 枚举子节点v
		int v = e[i].v, w = e[i].w;
		if (v != fa) {
			for (int j = k; ~j; --j) {	// 分配给u的能量
				for (int p = w; p <= j; ++p) {	// 分配给v的能量
					f[u][j] = max(f[u][j], f[u][j - p] + f[v][p - w]);	// 容量还有p - w
				}
			}
		}
	}
	for (int i = 0; i <= k; ++i) {	// 不要忘记算上u自己
		++f[u][i];
	}
}
int main() {
	ios :: sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> k;
	while (--n) {
		int u, v, w;
		cin >> u >> v >> w;
		add(u, v, w), add(v, u, w);
	}
	dfs(1, -1);
	cout << f[1][k] << '\n';
	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45

    树上差分前缀和

    给定 n n n的结点的树和 m m m条树上路径，求每个点被路径覆盖的次数，要求时间复杂度 O ( n l g n ) O(nlgn) O(nlgn)。

    我们知道连续区间加一个数可以用差分 O ( 1 ) O(1) O(1)维护，但树上路径并不是连续的，或者说是一条链。

    那可不可以将路径化成链呢？显然可以。令 l = l c a ( u , v ) l=lca(u,v) l=lca(u,v)，我们将 u → v u\to v u→v拆解成 u → l u\to l u→l和 v → l v\to l v→l再去掉 l l l，则利用差分：

    u -> l: ++d[u], --d[fa[l]];
v -> l: ++d[v], --d[fa[l]];
-l: ++d[fa[l]], --d[l];
=> ++d[u], ++d[v], --d[l], --d[fa[l]];

    • 1
    • 2
    • 3
    • 4

    不要忘记最终再做一次前缀和。

    #include 
using namespace std;
const int N = 1e5 + 5;
struct edge {
	int v, nxt;
} e[N << 1];
int head[N], cnt;
inline void add(int u, int v) {
	e[++cnt] = {v, head[u]}, head[u] = cnt;
}
int d[N], dep[N], fa[N][20];
void dfs(int u) {
	for (int i = head[u]; i; i = e[i].nxt) {
		int v = e[i].v;
		if (dep[v] == -1) {
			dep[v] = dep[u] + 1, fa[v][0] = u;
			dfs(v);
		}
	}
}
int lca(int u, int v) {
	if (dep[u] < dep[v]) {
		swap(u, v);
	}
	int k = 0;
	for (; (1 << k) <= dep[u]; ++k);
	--k;
	for (int i = k; ~i; --i) {
		if (dep[u] - (1 << i) >= dep[v]) {
			u = fa[u][i];
		}
	}
	if (u == v) {
		return u;
	}
	for (int i = k; ~i; --i) {
		if (fa[u][i] != fa[v][i]) {
			u = fa[u][i], v = fa[u][i];
		}
	}
	return fa[u][0];
}
void dfs1(int u, int fa) {
	for (int i = head[u]; i; i = e[i].nxt) {
		int v = e[i].v;
		if (v != fa) {
			dfs1(v, u);
			d[u] += d[v];
		}
	}
}
int main() {
	ios :: sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	memset(dep, -1, sizeof dep);
	int n, m, u, v;
	cin >> n;
	for (int i = 1; i < n; ++i) {
		cin >> u >> v;
		add(u, v), add(v, u);
	}
	dep[1] = 0;
	dfs(1);
	for (int i = 1; (1 << i) <= n; ++i) {
		for (int u = 1; u <= n; ++u) {
			fa[u][i] = fa[fa[u][i - 1]][i - 1];
		}
	}
	cin >> m;
	while (m--) {
		cin >> u >> v;
		int l = lca(u, v);
		++d[u], ++d[v], --d[l], --d[fa[l][0]];
	}
	dfs1(1, -1);
	for (int i = 1; i <= n; ++i) {
		cout << d[i] << '\n';
	}
	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80

    习题

    [ZJOI2008] 骑士

    将每个骑士与其厌恶的骑士连边，显然会构成一个基环树森林，问题就转化成了在基环树上找最大独立子集的问题，最大的问题就是找到树根。当然不可以让每个点作为根分别DP，我们设 f u , 0 / 1 f_u,_{0/1} fu​,0/1​为不选/选结点 u u u的答案。在环中找到一条边，令其一端点为根，另一端不选。点如何走向环？连边时连单向边即可，答案即为 m a x ( f u , 0 , f u , 1 ) max(f_u,_0,f_u,_1) max(fu​,0​,fu​,1​)。

    [HAOI2015] 树上染色

    此题思路极为巧妙。枚举点的贡献必然超时，则我们可以枚举边的贡献，也就是同色点对。设 f u , i f_u,_i fu​,i​为子树 u u u中有 i i i个黑点时边的贡献和。此题代码技巧也很多。

    今天的复习就到这里，感谢收看~

  • 相关阅读:
    剑指 Offer 50. 第一个只出现一次的字符
    metinfo_5.0.4 EXP Python脚本编写
    进程的优先级与LAMP项目部署实战
    使用 Certbot 为 Nginx 自动配置 SSL 证书
    你准备好了吗，9月19日Java21要来了
    网页在线打开PDF_网站中在线查看PDF之pdf.js
    Simulink| “双碳”背景下汽车减少碳排放建模与仿真
    操作系统知识点梳理-进程线程
    终极篇章_springMVC_文件上传和下载
    睡觉时，为啥有人喜欢穿袜子，有的人不穿？穿袜子睡觉好不好？
  • 原文地址：https://blog.csdn.net/yueyuedog/article/details/126256364