动态规划课程树型dp例题 题解
小G有一个大树
题意
给定一棵 n n n个节点的树，求树的重心。
思路
树的重心是指树中所有的点到某个点的距离之和中，到重心的距离之和是最小的（可能存在多个重心，距离之和相等）。
且树的重心满足：以树的重心为根时，所有子树的大小都不超过整棵树大小的一半。
详细的定义可以看oi-wiki https://oi-wiki.org/graph/tree-centroid/
维护每个节点
u
u
u的
s
z
sz
sz和
w
e
i
g
h
t
weight
weight分别表示：
u
u
u节点的子节点有多少个，以
u
u
u节点为根时最大的子树的节点数。
s
z
[
u
]
=
1
+
∑
s
z
[
v
]
w
e
i
g
h
t
[
u
]
=
m
a
x
(
m
a
x
{
s
z
[
v
]
}
,
?
n
?
s
z
[
u
]
)
sz[u]=1+\sum sz[v] \\ weight[u]=max(max\{sz[v]\},\ n-sz[u])
sz[u]=1+∑sz[v]weight[u]=max(max{sz[v]},?n?sz[u])
当
w
e
i
g
h
t
[
u
]
≤
n
2
weight[u]\le \frac{n}{2}
weight[u]≤2n?时，
u
u
u就为当前树的一个根。
AC的代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
int n, sz[N], weight[N];
int res = 1e4;
vector<int> G[N];
void dfs(int u, int fa) {
weight[u] = 0;
sz[u] = 1;
for (int v : G[u]) {
if (v == fa) continue;
dfs(v, u);
sz[u] += sz[v];
weight[u] = max(weight[u], sz[v]);
}
weight[u] = max(weight[u], n - sz[u]);
// 满足重心的定义
if (weight[u] <= n / 2) {
// 刷新答案
if (u < res) res = u;
}
}
int main() {
cin >> n;
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
G[u].push_back(v);
G[v].push_back(u);
}
dfs(1, -1);
cout << res << " " << weight[res];
return 0;
}
树上子链
题意
给定一颗有 n n n个节点的树，每个节点有一个权值 w i w_i wi?，求树上权值之和最大的一条链，并将这个权值之和输出。
思路
设节点 u u u的子节点集合为 V = { v } V=\{v\} V={v}，则经过节点 u u u并且由节点 u u u和 u u u的子树组成的最大权值链是 max ? i = 1 ∣ V ∣ { v a l [ v i ] } + S e c o n d ? max ? i = 1 ∣ V ∣ { v a l [ v i ] } + w [ u ] \max _{i=1}^{|V|}\{ val[v_i] \}+Second\ \max _{i=1}^{|V|}\{ val[v_i] \}+w[u] maxi=1∣V∣?{val[vi?]}+Second?maxi=1∣V∣?{val[vi?]}+w[u]， v a l [ v i ] val[v_i] val[vi?]表示从 v i v_i vi?向下搜索能得到的最大权值，如下图。
遍历所有的节点 u u u，并更新答案。
AC的代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5 + 10;
int n, w[N];
ll sz[N];
ll res = 0;
vector<int> G[N];
void dfs(int u, int fa) {
sz[u] = w[u];
ll maxn1 = 0, maxn2 = 0;
for(int v : G[u]) {
if(v == fa) continue;
dfs(v, u);
if(sz[v] > maxn1) {
maxn2 = maxn1;
maxn1 = sz[v];
} else if(sz[v] > maxn2) {
maxn2 = sz[v];
}
}
res = max(res, maxn1 + maxn2 + w[u]);
sz[u] += maxn1;
}
int main() {
cin >> n;
int maxn = -0x3f3f3f3f;
for(int i = 1; i <= n; i++) cin >> w[i], maxn = max(maxn, w[i]);
for(int i = 2; i <= n; i++) {
int u, v;
cin >> u >> v;
G[u].push_back(v);
G[v].push_back(u);
}
dfs(1, -1);
res = (res != 0) ? res : maxn;
cout << res;
return 0;
}
吉吉王国
题意
给定一个 n n n个节点的树，根节点为 1 1 1，每条边有一个权值。
要删除若干条边（设这个被删边的集合为 S { e d g e } S\{edge\} S{edge}），使得原树中的叶子节点都被去掉，且删除的边的权值之和不超过 m m m， ∑ i = 1 ∣ S { e d g e } ∣ v a l [ i ] ≤ m \sum_{i=1}^{|S\{edge\}|}val[i] \le m ∑i=1∣S{edge}∣?val[i]≤m， v a l [ i ] val[i] val[i]表示第 i i i条边的权值。
问删除的边中的最大值的最小值是多少，即最小化 max ? i = 1 ∣ S { e d g e } ∣ v a l [ i ] \max_{i=1}^{|S\{edge\}|}val[i] maxi=1∣S{edge}∣?val[i]。
思路
考虑二分答案， c h e c k ( k ) check(k) check(k)可以理解为所选边权不超过 k k k时，能否满足题目要求的两个条件：
- 原树中的叶子节点都被去掉。
- ∑ i = 1 ∣ S { e d g e } ∣ v a l [ i ] ≤ m \sum_{i=1}^{|S\{edge\}|}val[i] \le m ∑i=1∣S{edge}∣?val[i]≤m。
如下图，假设节点 U U U有 3 3 3个子节点 V 1 , V 2 , V 3 V_1,V_2,V_3 V1?,V2?,V3?，其中 V 1 V_1 V1?和 V 2 V_2 V2?是叶子节点：
若
U
U
U要满足不和叶子节点相连，必须要把叶子节点
V
1
V_1
V1?和
V
2
V_2
V2?删掉，而对于
V
3
V_3
V3?来说，可以删除
U
?
V
3
U-V_3
U?V3?（当权值
≤
k
\le k
≤k时），也可以让
V
3
V_3
V3?满足不和叶子节点相连。
d
p
[
u
]
=
∑
v
?
i
s
?
a
?
c
h
i
l
d
?
n
o
d
e
?
o
f
?
u
m
i
n
(
e
d
g
e
[
u
]
[
v
]
,
d
p
[
v
]
)
dp[u]=\sum_{v\ is\ a\ child\ node \ of\ u} min(edge[u][v],dp[v])
dp[u]=v?is?a?child?node?of?u∑?min(edge[u][v],dp[v])
AC的代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e3 + 10;
const int M = 2 * N;
const int inf = 0x3f3f3f3f;
int n, m;
int h[N], e[M], ne[M], f[M], idx;
int dp[N];
void add(int u, int v, int d) {
e[idx] = v, f[idx] = d, ne[idx] = h[u], h[u] = idx++;
}
void dfs(int u, int fa, int k) {
ll tmp = 0;
for(int i = h[u]; ~i; i = ne[i]) {
int v = e[i];
if(v == fa) continue;
dfs(v, u, k);
if(f[i] <= k)
tmp += min(f[i], dp[v]);
else tmp += dp[v];
}
if(tmp != 0)
dp[u] = min(1LL * dp[u], tmp);
}
bool check(int k) {
memset(dp, 0x3f, sizeof dp);
dfs(1, -1, k);
return dp[1] <= m;
}
int main() {
memset(h, -1, sizeof h);
cin >> n >> m;
for(int i = 1; i < n; i++) {
int u, v, d;
cin >> u >> v >> d;
add(u, v, d);
add(v, u, d);
}
// 二分答案
int l = 1, r = 1e3 + 10;
while(l < r) {
int mid = (l + r) / 2;
if(check(mid)) {
r = mid;
} else {
l = mid + 1;
}
}
if(r == 1e3 + 10) cout << "-1";
else cout << r;
return 0;
}
Rinne Loves Edges
题意
给定一棵有 n n n个节点、 m m m条边（每条边有一个权值）的树，并定义 s s s为关键点。
删除若干条边（设这个被删边的集合为 S { e d g e } S\{edge\} S{edge}），使得关键点不和树上的叶子节点相连，求被删除的边的权值之和的最小值， min ? ∑ i = 1 ∣ S { e d g e } ∣ v a l [ i ] \min \sum_{i=1}^{|S\{edge\}|}val[i] min∑i=1∣S{edge}∣?val[i]。
思路
相当于上一题的简化版，可以先把上一题写了，再看这个。
基本思路不变，少了几个限制，直接转移就行了。
d
p
[
u
]
=
∑
v
?
i
s
?
a
?
c
h
i
l
d
?
n
o
d
e
?
o
f
?
u
m
i
n
(
e
d
g
e
[
u
]
[
v
]
,
d
p
[
v
]
)
dp[u]=\sum_{v\ is\ a\ child\ node \ of\ u} min(edge[u][v],dp[v])
dp[u]=v?is?a?child?node?of?u∑?min(edge[u][v],dp[v])
AC的代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 10;
const int M = 2 * N;
const int inf = 1e16;
int n, m, s;
int h[N], e[M], ne[M], f[M], idx;
int dp[N];
void add(int u, int v, int d) {
e[idx] = v, f[idx] = d, ne[idx] = h[u], h[u] = idx++;
}
void dfs(int u, int fa) {
int sum = 0;
for (int i = h[u]; ~i; i = ne[i]) {
int v = e[i];
if (v == fa) continue;
dfs(v, u);
sum += min(f[i], dp[v]);
}
if (sum != 0) dp[u] = sum;
}
signed main() {
memset(h, -1, sizeof h);
cin >> n >> m >> s;
while (m--) {
int u, v, d;
cin >> u >> v >> d;
add(u, v, d);
add(v, u, d);
}
fill(dp + 1, dp + 1 + n, inf);
dfs(s, -1);
if (dp[s] == inf) dp[s] = 0;
cout << dp[s];
return 0;
}
[USACO 2008 Jan G]Cell Phone Network
题意
给定一个 n n n个节点的树，现在要在若干个节点上建信号站，如果某一个点上有信号站，则这个点和相连的点都能收到信号。
问最少建多少个信号站。
思路
最少点覆盖树的经典问题。
将一个点分成 3 3 3种状态：
- d p [ u ] [ 0 ] dp[u][0] dp[u][0]：在这个点建立信号站。
- d p [ u ] [ 1 ] dp[u][1] dp[u][1]：该点被父节点的信号覆盖。
- d p [ u ] [ 2 ] dp[u][2] dp[u][2]：该点被子节点（至少有一个子节点）的信号覆盖。
然后考虑状态转移：
- 对于叶子节点来说，不存在子节点，可以直接将 d p [ u ] [ 2 ] dp[u][2] dp[u][2]设为无穷大 i n f inf inf。
- 当 u u u节点建信号站时，子节点 v v v可以 3 3 3中状态的任意一种。
d p [ u ] [ 0 ] = 1 + ∑ v ∈ G [ u ] ? ∧ ? v ≠ f a min ? { d p [ v ] [ 0 ] , d p [ v ] [ 1 ] , d p [ v ] [ 2 ] } dp[u][0]=1+\sum_{v \in G[u]\ \wedge \ v\neq fa} \min\{dp[v][0],dp[v][1],dp[v][2]\} dp[u][0]=1+v∈G[u]?∧?v?=fa∑?min{dp[v][0],dp[v][1],dp[v][2]}
- u u u节点被父节点的信号覆盖，因此子节点 v v v不能被 u u u的信号覆盖。
d p [ u ] [ 1 ] = ∑ v ∈ G [ u ] ? ∧ ? v ≠ f a min ? { d p [ v ] [ 0 ] , d p [ v ] [ 2 ] } dp[u][1]=\sum_{v \in G[u]\ \wedge \ v\neq fa} \min\{dp[v][0],dp[v][2]\} dp[u][1]=v∈G[u]?∧?v?=fa∑?min{dp[v][0],dp[v][2]}
- u u u节点被某一子节点 k k k的信号覆盖时，其他子节点 v ≠ k v\neq k v?=k不能被 u u u的信号覆盖。
d p [ u ] [ 2 ] = min ? k ∈ G [ u ] ? ∧ ? k ≠ f a { d p [ k ] [ 0 ] + ∑ v ∈ G [ u ] ? ∧ ? v ≠ f a ? ∧ ? v ≠ k min ? { d p [ v ] [ 0 ] , d p [ v ] [ 2 ] } } dp[u][2]=\min_{k \in G[u]\ \wedge \ k\neq fa} \{dp[k][0] + \sum_{v \in G[u]\ \wedge \ v\neq fa\ \wedge \ v\neq k} \min\{dp[v][0],dp[v][2]\}\} dp[u][2]=k∈G[u]?∧?k?=famin?{dp[k][0]+v∈G[u]?∧?v?=fa?∧?v?=k∑?min{dp[v][0],dp[v][2]}}
? 可以发现，这个式子后边的
∑
\sum
∑和
d
p
[
u
]
[
1
]
dp[u][1]
dp[u][1]的很像，可以将式子转化，从而降低计算的复杂度。
d
p
[
u
]
[
2
]
=
min
?
k
∈
G
[
u
]
?
∧
?
k
≠
f
a
{
d
p
[
k
]
[
0
]
+
d
p
[
u
]
[
1
]
?
min
?
{
d
p
[
k
]
[
0
]
,
d
p
[
k
]
[
2
]
}
}
dp[u][2]=\min_{k \in G[u]\ \wedge \ k\neq fa} \{dp[k][0] + dp[u][1] - \min\{dp[k][0],dp[k][2]\}\}
dp[u][2]=k∈G[u]?∧?k?=famin?{dp[k][0]+dp[u][1]?min{dp[k][0],dp[k][2]}}
AC的代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10;
const int inf = 0x3f3f3f3f;
int n, dp[N][3];
vector<int> G[N];
void dfs(int u, int fa) {
dp[u][0] = 1;
for (int v : G[u]) {
if (v == fa) continue;
dfs(v, u);
dp[u][0] += min(dp[v][0], min(dp[v][1], dp[v][2]));
dp[u][1] += min(dp[v][0], dp[v][2]);
}
dp[u][2] = inf;
for (int v : G[u]) {
dp[u][2] = min(dp[u][2], dp[v][0] + dp[u][1] - min(dp[v][0], dp[v][2]));
}
}
int main() {
cin >> n;
for (int i = 1, v, u; i < n; i++) {
cin >> u >> v;
G[u].push_back(v);
G[v].push_back(u);
}
dfs(1, -1);
cout << min(dp[1][0], dp[1][2]);
return 0;
}
二叉苹果树
题意
给定一个有 n n n个节点且根节点为 1 1 1的树，树上每条边都有一个边权。
现在要减掉一些树枝，使得最后保留 q q q个树枝（树枝和根节点 1 1 1要连在一起）。
问保留的树枝权值之和最大为多少。
思路
树上背包。
定义 d p [ i ] [ j ] dp[i][j] dp[i][j]为以 i i i节点为根节点的子树中，保留 j j j个树枝得到的最大权值。
状态转移方程为：（枚举 i , j i,j i,j）
d p [ u ] [ i ] = m a x ( d p [ u ] [ i ] , d p [ u ] [ i ? j ? 1 ] + d p [ v ] [ j ] + w [ u ] [ v ] ) dp[u][i]=max(dp[u][i],dp[u][i-j-1]+dp[v][j] + w[u][v]) dp[u][i]=max(dp[u][i],dp[u][i?j?1]+dp[v][j]+w[u][v])。
AC的代码
#include <bits/stdc++.h>
using namespace std;
const int N = 100 + 10;
int n, q, dp[N][N];
int w[N][N];
vector<int> G[N];
void dfs(int u, int fa) {
for (int v : G[u]) {
if (v == fa) continue;
dfs(v, u);
}
for (int v : G[u]) {
if (v == fa) continue;
for (int i = q; i >= 1; i--)
for (int j = 0; j < i; j++)
dp[u][i] = max(dp[u][i], dp[u][i - j - 1] + dp[v][j] + w[u][v]);
}
}
int main() {
cin >> n >> q;
for (int i = 1, u, v, d; i < n; i++) {
cin >> u >> v >> d;
G[u].push_back(v);
G[v].push_back(u);
w[u][v] = w[v][u] = d;
}
dfs(1, -1);
cout << dp[1][q];
return 0;
}
没有上司的舞会
题意
给定一个有 n n n个节点的树，每个节点有一个权值，按照以下要求选出一些节点，使得权值和最大（注意权值有负数）。
- 当选中点 u u u时，不能选中和 u u u相邻的儿子节点。
思路
当选中
u
u
u时，儿子节点一定不能选：
d
p
[
u
]
[
1
]
=
∑
v
?
i
s
?
a
?
c
h
i
l
d
?
n
o
d
e
?
o
f
?
u
d
p
[
v
]
[
0
]
dp[u][1] = \sum_{v\ is\ a\ child\ node \ of\ u} dp[v][0]
dp[u][1]=v?is?a?child?node?of?u∑?dp[v][0]
当没选中
u
u
u时，儿子节点可选也可以不选：
d p [ u ] [ 0 ] = ∑ v ? i s ? a ? c h i l d ? n o d e ? o f ? u max ? ( d p [ v ] [ 0 ] , d p [ v ] [ 1 ] ) dp[u][0] = \sum_{v\ is\ a\ child\ node \ of\ u} \max(dp[v][0], dp[v][1]) dp[u][0]=v?is?a?child?node?of?u∑?max(dp[v][0],dp[v][1])
AC的代码
#include <bits/stdc++.h>
using namespace std;
const int N = 6000 + 10;
int n, dp[N][2];
int vis[N];
vector<int> G[N];
void dfs(int u, int fa) {
if (!G[u].size()) return;
int sum = 0;
for (int v : G[u]) {
if (v == fa) continue;
dfs(v, u);
dp[u][0] += max(dp[v][0], dp[v][1]);
dp[u][1] += dp[v][0];
}
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> dp[i][1];
for (int i = 1, u, v; i <= n; i++) {
cin >> u >> v;
if (!u && !v) break;
G[u].push_back(v);
G[v].push_back(u);
vis[u] = 1;
}
int root = 1;
while (vis[root]) root++;
dfs(root, -1);
cout << max(dp[root][0], dp[root][1]);
return 0;
}
Strategic game
题意
给定一个有 n n n个节点的树，选定一些点定义为关键点，使得每一条边的两端至少有一个关键点。
思路
经典题目，可以先把[USACO 2008 Jan G]Cell Phone Network补了，再看这个。
当没选中
u
u
u时，儿子节点必须选：
d
p
[
u
]
[
0
]
=
∑
v
?
i
s
?
a
?
c
h
i
l
d
?
n
o
d
e
?
o
f
?
u
d
p
[
v
]
[
1
]
;
dp[u][0] = \sum_{v\ is\ a\ child\ node \ of\ u} dp[v][1];
dp[u][0]=v?is?a?child?node?of?u∑?dp[v][1];
当选中
u
u
u时，儿子节点可选也可以不选：
d
p
[
u
]
[
1
]
=
∑
v
?
i
s
?
a
?
c
h
i
l
d
?
n
o
d
e
?
o
f
?
u
m
i
n
(
d
p
[
v
]
[
0
]
,
d
p
[
v
]
[
1
]
)
;
dp[u][1] =\sum_{v\ is\ a\ child\ node \ of\ u} min(dp[v][0], dp[v][1]);
dp[u][1]=v?is?a?child?node?of?u∑?min(dp[v][0],dp[v][1]);
AC的代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1500 + 10;
int n, dp[N][2], vis[N];
vector<int> G[N];
void dfs(int u) {
dp[u][1] = 1;
for (int i = 0; i < G[u].size(); i++) {
int v = G[u][i];
dfs(v);
dp[u][0] += dp[v][1];
dp[u][1] += min(dp[v][0], dp[v][1]);
}
}
int main() {
while (cin >> n) {
memset(vis, 0, sizeof vis);
memset(dp, 0, sizeof dp);
for (int i = 0; i < n; i++) {
int u, v, len;
scanf("%d:(%d)", &u, &len);
G[u].clear();
while (len--) {
cin >> v;
G[u].push_back(v);
vis[v] = 1;
}
}
int root = 0;
while (vis[root]) root++;
dfs(root);
cout << min(dp[root][0], dp[root][1]) << "\n";
}
return 0;
}