樹形DP
例題
樹的直徑
一棵樹中，最大的\(dist[x][y]\), \(x, y \in V\)
求解方法：
- 任取一個點作為起點\(r\), 找到離\(r\)最遠的一個點\(a\)
- 找到一個離\(a\)最遠的一個點\(b\)
\(dis[a][b]\)為樹的直徑
任取一點\(a\)為起點， 找到離他最遠的點\(u\), \(u\)一定是直徑的某個端點
證明：
設\(dist[b][c]是一個樹的直徑\), 如下圖：
假設我們根據上述條件找到的\(<a, u>\)和 \(<b, c>\) 這兩個路徑不相交。
顯然這種情況下, \(u\)在樹的路徑中
若兩個路徑相交：
綜上，通過該選法找到的\(u\)一定為樹上直徑上的一點。
如何進行動態規劃：
我們考慮當前點為樹的直徑上高度最低的一個點\(u\)（最上面的一個點）：
令\(dist[v]\)表示從\(v\)到葉子節點的一條路徑中的最大值
- 當該點為直徑上的終點時，樹的直徑為\(w(u,v) + dist[v]\)， \(v\) 為\(max(dist[v_i]), v_i \in S_u\)
- 當該點位直徑上的一個中間點時，樹的直徑為\(w(u, v) + dist[v_1] + dist[v_2]\) 其中 \(v_i \in S_u\), 且\(v_1\)為\(dist[v_i]\)中最大值，\(v_2\)為次大值
狀態轉移方程:
\[f[u] = dist[v_1] + dist[v_2], v_i \in S_u \\
d_{tree} = max(f[u]),u \in G
\]
#include <bits/stdc++.h>
using i64 = long long;
const int N = 1e4 + 10, M = 2e4 + 10;
int n;
int h[N], ne[M], e[M], w[M], idx;
int ans;
void add(int a, int b, int c) {
ne[idx] = h[a], h[a] = idx, e[idx] = b, w[idx ++] = c;
}
int dfs(int u, int fa) {
int d1 = 0, d2 = 0;
for (int i = h[u]; ~i; i = ne[i]) {
int v = e[i];
if (v == fa) continue;
int d = dfs(v, u) + w[i];
if (d >= d1) d2 = d1, d1 = d;
else if (d > d2) d2 = d;
}
ans = std::max(ans, d1 + d2);
return d1;
}
int main() {
memset(h, -1, sizeof h);
std::cin >> n;
for (int i = 1; i < n; i ++) {
int a, b, c;
std::cin >> a >> b >> c;
add(a, b, c), add(b, a, c);
}
dfs(1, -1);
std::cout << ans;
}
樹的中心
對于樹\(G<V, E>\), 求樹中的任意一點到其他點的最大距離的最小值。
我們先任選一點為起點，對于任一點的路徑可以分為向上走的最遠距離和向下走的最遠距離，我們設\(d1[x], d2[x]\)分別為\(x\)結點向下走的最大值和次大值, \(p1[x]\)為最大值對應的點。
顯然我們可以先\(O(V + E)\)的預處理任意點的\(d1[x], d2[x], p1[x]\)值， 對于向上走的路徑我們設\(up[x]\)為\(x\)結點向上走的最遠距離， 那么我們可以更新：
其中\(fa\)為\(x\)的父節點
\[up[x] = max(d1[fa], up[fa]) + w[i], x \ne p1[x] \\
up[x] = max(d2[fa], up[fa]) + w[i], x = p1[x]
\]
#include <bits/stdc++.h>
using i64 = long long;
const int N = 1e4 + 10, M = N * 2, INF = 0x3f3f3f3f;
int h[N], e[M], ne[M], w[M], idx;
int d1[N], d2[N], p1[N], p2[N], up[N];
bool leaf[N];
int n;
void add(int a, int b, int c) {
ne[idx] = h[a], h[a] = idx, e[idx] = b, w[idx ++] = c;
}
int dfs1(int u, int fa) {
if (h[u] == -1) {
return leaf[u] = true, 0;
}
d1[u] = d2[u] = -INF;
for (int i = h[u]; ~i; i = ne[i]) {
int v = e[i];
if (v == fa) continue;
int d = dfs1(v, u) + w[i];
if (d >= d1[u]) {
d2[u] = d1[u], d1[u] = d;
p1[u] = v;
}
else if (d > d2[u]) d2[u] = d;
}
return d1[u];
}
void dfs2(int u, int fa) {
for (int i = h[u]; ~i; i = ne[i]) {
int v = e[i];
if (v == fa) continue;
if (p1[u] == v) up[v] = std::max(up[u], d2[u]) + w[i];
else up[v] = std::max(up[u], d1[u]) + w[i];
dfs2(v, u);
}
}
int main() {
memset(h, -1, sizeof h);
std::cin >> n;
for (int i = 1; i <= n - 1; i ++) {
int a, b, c;
std::cin >> a >> b >> c;
add(a, b, c), add(b, a, c);
}
dfs1(1, -1);
dfs2(1, -1);
int ans = INF;
for (int i = 1; i <= n; i ++) {
if (leaf[i]) {
ans = std::min(ans, up[i]);
} else ans = std::min(ans, std::max(up[i], d1[i]));
}
std::cout << ans;
}
數字轉換
可以\(O(\ln(n))\)的預處理后，在進行建樹
\(O(V + E)\)的求樹的直徑
#include <bits/stdc++.h>
using i64 = long long;
const int N = 1e5 + 10, M = N * 2;
int n, a[N];
int h[N], ne[M], e[M], idx;
bool st[N];
int ans;
void add(int a, int b) {
ne[idx] = h[a], h[a] = idx, e[idx ++] = b;
}
void init() {
for (int i = 1; i <= n; i ++) {
for (int j = i + i; j <= n; j += i) {
a[j] += i;
}
}
for (int i = 2; i <= n; i ++) {
if (i > a[i])
add(i, a[i]), add(a[i], i);
}
}
int dfs(int u, int fa) {
int d1 = 0, d2 = 0;
for (int i = h[u]; ~i; i = ne[i]) {
int v = e[i];
// std::cout << v << "\n";
if (v == fa) continue;
st[v] = true;
int d = dfs(v, u) + 1;
if (d >= d1) d2 = d1, d1 = d;
else if (d > d2) d2 = d;
}
ans = std::max(ans, d1 + d2);
return d1;
}
int main() {
memset(h, -1, sizeof h);
std::cin >> n;
init();
for (int i = 2; i <= n; i ++) {
if (!st[i]) {
dfs(i, -1), st[i] = true;
// std::cout << ans << "\n";
}
}
std::cout << ans;
}
二叉蘋果樹
有依賴的背包問題
我們把可以保留的邊數看作體積，然后按父節點可以給子節點留下的體積最多是多少，進行分組背包
設\(f[u][j]\)為以\(u\)為根節點，可以保留的邊數為\(j\)的情況下的最大蘋果數量
\[f[u][j] = max(f[u][j], f[u][j - k - 1] + f[v][k] + w[i]), 0 \le k < j, 0 \le j \le m
\]
復雜度 \(O(N \times V \times V)\)
#include <bits/stdc++.h>
using i64 = long long;
const int N = 110, M = N * 2;
int h[N], e[M], ne[M], w[M], idx;
int n, m;
int f[N][N];
void add(int a, int b, int c) {
ne[idx] = h[a], h[a] = idx, e[idx] = b, w[idx ++] = c;
}
void dfs(int u, int fa) {
for (int i = h[u]; ~i; i = ne[i]) {
int v = e[i];
if (v == fa) continue;
dfs(v, u);
for (int j = m; j >= 0; j --) {
for (int k = 0; k < j; k ++) {
f[u][j] = std::max(f[u][j], f[u][j - k - 1] + f[v][k] + w[i]);
}
}
}
}
int main() {
memset(h, -1, sizeof h);
std::cin >> n >> m;
for (int i = 1; i < n; i ++) {
int a, b, c;
std::cin >> a >> b >> c;
add(a, b, c), add(b, a, c);
}
dfs(1, -1);
std::cout << f[1][m];
}
戰略游戲
沒有上司的舞會 是每條邊上最多選擇一個點。最大權值
戰略游戲 是 每條邊上最少選擇一個點。最大權值
我們設
在以\(i\)為根的子樹中：
\(f[i][0]\) 表示選定不選\(i\)點的最小代價
\(f[i][1]\) 表示選定\(i\)點的最小代價
按照題目的設定條件，每個邊都需要被選定的點覆蓋, 設\(u\)的兒子結點集合為\(S_u\)
則狀態機的轉移方程為：
\[f[u][0] = \sum \limits_{v \in S_u} f[v][1] \\
f[u][1] = \sum \limits_{v \in S_u} max(f[u][0], f[u][1])
\]
#include <bits/stdc++.h>
using i64 = long long;
const int N = 1510, M = N;
int h[N], e[M], ne[M], idx;
int f[N][2];
bool st[N];
void add(int a, int b) {
ne[idx] = h[a], h[a] = idx, e[idx ++] = b;
}
void dfs(int u) {
f[u][0] = 0;
f[u][1] = 1;
for (int i = h[u]; ~i; i = ne[i]) {
int v = e[i];
dfs(v);
f[u][0] += f[v][1];
f[u][1] += std::min(f[v][0], f[v][1]);
}
}
int main() {
int n;
while (std::cin >> n) {
memset(h, -1, sizeof h);
memset(st, false, sizeof st);
idx = 0;
for (int i = 1; i <= n; i ++) {
int id, cnt;
scanf("%d:(%d)", &id, &cnt);
while (cnt --) {
int ver;
scanf("%d", &ver);
add(id, ver);
st[ver] = true;
}
}
int root = 0;
while (st[root]) root ++;
dfs(root);
printf("%d\n", std::min(f[root][0], f[root][1]));
}
}
皇宮看守
與上一個題目不同的是，這里是點覆蓋點。
在點覆蓋邊中，如果一個父節點沒有被選擇，那么他的所有子節點都要被選擇去覆蓋與父節點相連的邊。
但是在點覆蓋點當中，一個父節點沒有被選擇，那么他的子節點至少有一個被選擇，是一個組合問題。
我們考慮狀態轉移，設定狀態機：
屬性都為\(Min\)代價
\(f[u][0]\) 表示該點被其父節點覆蓋
\(f[u][1]\) 表示該點被其子節點覆蓋
\(f[u][2]\) 表示該點被覆蓋
那么我們可以得到正確的狀態轉移方程:
\[f[u][0] = \sum \limits_{v \in S_u} min(f[v][2], f[v][1]) \\
f[u][2] = \sum \limits_{v \in S_u} min(f[v][0], f[v][1], f[v][2]) \\
f[u][1] = \sum \limits_{v \in S_u, k \in S_u, v \ne k} f[k][2] + min(f[v][1], f[v][2]), \\
\]
#include <bits/stdc++.h>
using i64 = long long;
const int N = 1510;
int h[N], e[N], ne[N], w[N], idx;
int n;
bool st[N];
int f[N][3];
void add(int a, int b) {
ne[idx] = h[a], h[a] = idx, e[idx ++] = b;
}
void dfs(int u) {
f[u][2] = w[u];
int sum = 0;
for (int i = h[u]; ~i; i = ne[i]) {
int v = e[i];
dfs(v);
f[u][0] += std::min(f[v][2], f[v][1]);
f[u][2] += std::min(f[v][0], std::min(f[v][1], f[v][2]));
sum += std::min(f[v][1], f[v][2]);
}
f[u][1] = 1e9;
for (int i = h[u]; ~i; i = ne[i]) {
int v = e[i];
f[u][1] = std::min(f[u][1], sum - std::min(f[v][1], f[v][2]) + f[v][2]);
}
}
int main() {
std::cin >> n;
memset(h, -1, sizeof h);
for (int i = 1; i <= n; i ++) {
int id, cost, cnt;
std::cin >> id >> cost >> cnt;
w[id] = cost;
while (cnt --) {
int ver;
std::cin >> ver;
add(id, ver);
st[ver] = true;
}
}
int root = 1;
while (st[root]) root ++;
dfs(root);
std::cout << std::min(f[root][1], f[root][2]);shuwei 
浙公網安備 33010602011771號