數據結構與算法學習筆記----動態規劃·樹形DP

@@ author: 明月清了個風
@@ first publish time: 2025.6.4

ps??樹形動態規劃（樹形DP）是處理樹結構問題的一種動態規劃方法，特征也很明顯，會有一個樹形結構，其實是DFS的優化。

Acwing 1072. 樹的最長路徑

給定一棵樹，樹中包含$n$個節點(編號$1～n$)和$n?1$條無向邊，每條邊都有一個權值。

現在請你找到樹中最長的一條路徑。

換句話說，要找到兩個點，使得他們之間的距離最遠。

輸入格式

第一行包含整數$n$，

接下來$n?1$行，每行包含三個整數$a_i,b_i,c_i$，表示點$a_i$和$b_i$之間存在一條權值為$c_i$的邊。

輸出格式

輸出一個整數，表示樹的最長路徑的長度。

數據范圍

$1\le n\le 10000$,

$1\le a_i,b_i\le n$,

$1\le c_i\le 10^5$

思路

找樹的最長路徑(直徑)有一個通用的思路：

1. 任選一個點，找出離這個點最遠的點$u$。
2. 再找到離$u$最遠的點$v$

$u$與$v$之間的路徑就是直徑。

證明如下；

假設任選的這個點是$a$，找到離他最遠的點為$u$，只要證明$u$是某條直徑的一個端點就行了。

假設一條直徑為$bc$，那他可能會與$au$之間沒有交點，由于樹是連通的，所以從$a$開始走一定能走到$c$點，假設這條路徑是$axyc$，其中$x$在$au$上，$y$在$bc$上，由于$u$是離$a$最遠的點，那么$xu$的長度大于等于$xy+yc$，那么就有$by+yx+xu\ge yc$，因此$bu$之間的距離一定大于等于$bc$的長度，因此$bu$一定是一條直徑的端點。

另一種情況是兩條線相交，假設交點是$x$，那么由于$u$是離$a$最遠的點，就有$ux\ge xc$，那么$bx+xu\ge bc$，因此$u$也一定是一條直徑的端點。

由于這道題目并沒有指定根節點，因此可以任選一個點將整棵樹構建起來，然后對于每個點記錄經過該點的最長路徑。

對于一個點的最長路徑，對于每個點來說可以分為兩種情況，一種是往下走，一種是往上走。就是枚舉他的每個子節點存的最大距離再加上他到這個子節點的距離；另一種情況是穿過一個點的路徑，那么就可以計算這個點往下的最長的路徑以及第二長的路徑相加。

代碼

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>using namespace std;const int N = 10010, M = N * 2;int n;
int h[N], e[M], ne[M], w[M], idx;
int ans;void add(int a, int b, int c)
{w[idx] = c, e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}int dfs(int u, int father)
{int dist = 0;int d1 = 0, d2 = 0;for(int i = h[u]; i != -1; i = ne[i]){int j = e[i];if(j == father) continue;int d = dfs(j, u) + w[i];dist = max(dist, d);if(d >= d1){d2 = d1;d1 = d;} else if(d > d2) d2 = d;}ans = max(ans, d1 + d2);return dist;
}int main()
{cin >> n;memset(h, -1, sizeof h);for(int i = 0; i < n - 1; i ++){int a, b, c;cin >> a >> b >> c;add(a, b, c), add(b, a, c);}dfs(1, -1);cout << ans << endl;return 0;
}

Acwing 1073. 樹的中心

給定一棵樹，樹中包含$n$個節點(編號$1～n$)和$n?1$條無向邊，每條邊都有一個權值。

請你在樹中找到一個點，使得該點到樹中其他結點的最遠距離最近。

輸入格式

第一行包含整數$n$，

接下來$n?1$行，每行包含三個整數$a_i,b_i,c_i$，表示點$a_i$和$b_i$之間存在一條權值為$c_i$的邊。

輸出格式

輸出一個整數，表示所求點到樹中其他結點的最遠距離。

數據范圍

$1\le n\le 10000$,

$1\le a_i,b_i\le n$,

$1\le c_i\le 10^5$

思路

與上一題一樣，對于樹中的一點有向上走與向下走兩種方案，每個點都記錄一個向上走與向下走的最大值，假設點$2$向其父節點$1$走，那么這就是向上走，在$1$點可以繼續向上走，也可以向下不經過點$2$的子節點走，若向下走，那就要考慮點$2$是否是向下走的最大長度，如果是，那就使能選擇次大值更新。

這一題復雜的地方在于，更新的過程同時用到了子節點更新父節點和父節點更新子節點。

代碼

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>using namespace std;const int N = 100010, M = N * 2, inf = 0x3f3f3f3f;int n;
int h[N], e[M] ,w[M], ne[M], idx;
int d1[N], d2[N], up[N];
int p1[N], p2[N];void add(int a, int b, int c)
{e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}int dfs_d(int u, int father)
{if(h[u] == -1) return 0;d1[u] = d2[u] = -inf;for(int i = h[u]; i != -1; i = ne[i]){int j = e[i];if(j == father) continue;int d = dfs_d(j, u) + w[i];if(d >= d1[u]){d2[u] = d1[u], d1[u] = d;p2[u] = p1[u], p1[u] = j; // 記錄最大值和次大值是從向哪個子節點走的} else if(d > d2[u])d2[u] = d, p2[u] = j;}if(d1[u] == -inf) d1[u] = d2[u] = 0; // 如果是葉子結點無法往下，置為0return d1[u];
}int dfs_u(int u, int father)
{if(h[u] == -1) return 0;for(int i = h[u]; i != -1; i = ne[i]){int j = e[i];if(j == father) continue;if(p1[u] == j) up[j] = max(up[u], d2[u]) + w[i];else up[j] = max(up[u], d1[u]) + w[i];dfs_u(j, u);}
}int main()
{cin >> n;memset(h, -1, sizeof h);for(int i = 0; i < n - 1; i ++){int a, b, c;cin >> a >> b >> c;add(a, b, c), add(b, a, c);}dfs_d(1, -1);dfs_u(1, -1);int res = inf;for(int i = 1; i <= n; i ++) res = min(res, max(up[i], d1[i]));cout << res << endl;return 0;}

Acwing 1075. 數字轉換

如果一個數$x$的約數之和$y$(不包括他本身)比他本身小，那么$x可以變成$$y$，$y$也可以變成$x$。

例如$4$可以變成$3$，$1$可以變成$7$

限制所有數字變換在不超過$n$的正整數范圍內進行，求不斷進行數字變換且不出現重復數字的最多變換步數。

輸入格式

輸入一個正整數$n$。

輸出格式

輸出斷進行數字變換且不出現重復數字的最多變換步數

數據范圍

$1\le n\le 50000$

思路

對于每個數$x$都會有一個約數之和$y$與之對應，且$x$到$y$的關系是唯一的，但需要注意的是$y$可能會對應于多個數，因此要將$y$作為父節點。那么對于所有數就可以構建出一堆樹(注意不是一棵樹，因為不一定所有數都能連通)，最多變換步數就是這堆樹中最長的樹的直徑，就是上面的第一題。

問題就是建樹，也就是找到$1～n$中所有數的約數之和。當然可以枚舉每個數進行計算（試除法），但是如果$n$的范圍進一步擴大就會超時。可以反向思考，不是求每個數的約數是哪些數，而是求每個數是哪些數的約數，也就是枚舉每個數的倍數

for(int i = 1; i <= n; i ++)for(int j = 2; j * i <= n; j ++)  // 從2開始枚舉

這樣的時間復雜度是$n\ln n$，因為$n+\frac{n}{2}+\frac{n}{3}+?$是一個調和級數，

代碼

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>using namespace std;const int N = 50010;int n;
int sum[N];
int h[N], e[N], ne[N], idx;
bool st[N];
int ans;void add(int a, int b)
{e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}int dfs(int u)
{int d1 = 0, d2 = 0;for(int i = h[u]; i != -1; i = ne[i]){int j = e[i];int d = dfs(j) + 1;if(d >= d1) d2 = d1, d1 = d;else if(d > d2) d2 = d;}ans = max(ans, d1 + d2);return d1;
}int main()
{cin >> n;memset(h, -1, sizeof h);for(int i = 1; i <=n; i ++)for(int j = 2; j <= n / i; j ++)sum[i * j] += i;for(int i = 2; i <= n; i ++)  // 建立邊的時候要從2開始，因為對于1來說，他會和0建邊，題目要求是正整數。if(sum[i] < i){add(sum[i], i);st[i] = true;}for(int i = 1; i <= n; i ++)if(!st[i])dfs(i);cout << ans << endl;return 0;
}

Acwing 1074. 二叉蘋果樹

有一顆蘋果樹，如果樹枝有分岔，一定是分兩叉，即沒有只有一個兒子的節點。

這棵樹共$N$個節點，編號為$1$至$N$，樹根編號一定是$1$。

我們用一根樹枝兩端連接的節點編號描述一根樹枝的位置。

一棵蘋果樹的樹枝太多了，需要剪枝，但是一些樹枝上長有蘋果，給定需要保留的樹枝數量，求最多能留住多少蘋果，這里的保留是指最終與$1$號點連通。

輸入格式

第一行包含兩個整數$N$和$Q$，分別表示樹的節點數以及要保留的樹枝數量。

接下來$N?1$行描述樹枝信息，每行三個整數，前兩個是它連接的節點的編號，第三個數是這根樹枝上蘋果數量。

輸出格式

輸出僅一行，表示最多能留住的最多的蘋果數量。

數據范圍

$1<Q<N\le 100$

每根樹枝上蘋果不超過$30000$個。

思路

在[背包模型四](數據結構與算法學習筆記（Acwing提高課）----動態規劃·背包模型(四）-CSDN博客)中講過一道有依賴的背包問題，其實這道題和那道題是一樣的，將蘋果數量放到每個點上，要選擇一個點就要選擇它的父節點，將所有點的體積看為$1$，總的體積就是$Q$。

但是這題可以進一步簡化，使用$f[i][j]$表示以$i$為根的子樹中選擇$j$個樹枝的最大價值。

對于狀態劃分來說，對于每個具有兩個分岔的小子樹，將其兩個子節點看成是一個分組背包問題里的兩個物品組，也就是對于以$i$為根的子樹有兩個物品$s_1$與$s_2$，劃分為在$s_1$中選擇$0$條邊，那就是$f[s_1][0]$；選擇$1$條邊，那就是$f[s_1][1]$;以此類推，最多是$f[s_1][j?1]$，因為要選擇$s_1$就要選擇$i$，也就是必選$i\to j$這條邊，當然計算的時候要加上這條邊的權重。對于子樹$s_2$也是一樣的。

代碼

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>using namespace std;const int N = 110, M = N * 2;int n, m;
int f[N][N];
int h[N], e[M], ne[M], w[M], idx;void add(int a, int b, int c)
{w[idx] = c, e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}void dfs(int u, int father)
{for(int i = h[u]; i != -1; i = ne[i])  // 枚舉物品組{if(e[i] == father) continue;dfs(e[i], u);for(int j = m; j >= 0; j --) // 體積for(int k = 0; k < j; k ++) // 決策f[u][j] = max(f[u][j], f[u][j - k - 1] + f[e[i]][k] + w[i]);}
}int main()
{cin >> n >> m;memset(h, -1, sizeof h);for(int i = 0; i < n - 1; i ++){int a, b, c;cin >> a >> b >> c;add(a, b, c), add(b, a, c);}dfs(1, -1);cout << f[1][m] << endl;return 0;
}

Acwing 323. 戰略游戲

鮑勃喜歡玩電腦游戲，特別是戰略游戲，但有時他找不到解決問題的方法，這讓他很傷心。

現在他有以下問題。

他必須保護一座中世紀城市，這條城市的道路構成了一棵樹。

每個節點上的士兵可以觀察到所有和這個點相連的邊。

他必須在節點上放置最少數量的士兵，以便他們可以觀察到所有的邊。

你能幫助他嗎？

例如，下面的樹：

只需要放置$1$名士兵（在節點$1$處），就可觀察到所有的邊。

輸入格式

輸入包含多組測試數據，每組測試數據用以描述一棵樹。

對于每組測試數據，第一行包含整數$N$，表示樹的節點數目。

接下來 $N$ 行，每行按如下方法描述一個節點。

節點編號：(子節點數目) 子節點 子節點 …

節點編號從 $0$ 到 $N?1$，每個節點的子節點數量均不超過$10$，每個邊在輸入數據中只出現一次。

輸出格式

對于每組測試數據，輸出一個占據一行的結果，表示最少需要的士兵數。

數據范圍

$0<N\le 1500$

思路

這道題的題意是對于一顆樹，選擇最少的節點數覆蓋所有的邊，這個其實和沒有上司的舞會很像，在沒有上司的舞會中，我們求的是每條邊上最多僅選擇一個點求最大值，屬于最大獨立集問題，而這道題中，每條邊上至少選擇一個點求最小值，這兩個是對稱的問題。

狀態計算和狀態轉移也很簡單，直接看代碼叭。

代碼

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>using namespace std;const int N = 1600;int n;
int f[N][2];
int h[N], e[N], ne[N], idx;
bool st[N];void add(int a, int b)
{e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}void dfs(int u)
{f[u][0] = 0;f[u][1] = 1;for(int i = h[u]; i != -1; i = ne[i]){int j = e[i];dfs(j);f[u][0] += f[j][1];f[u][1] += min(f[j][0], f[j][1]);}
}int main()
{while(scanf("%d", &n) != -1){idx = 0;memset(h, -1, sizeof h);memset(st, 0, sizeof st);for(int i = 0; i < n; i ++){int cnt;int id;scanf("%d:(%d)", &id, &cnt);while(cnt --){int ver;cin >> ver;add(id, ver);st[ver] = true;}}int root = 0;while(st[root]) root ++;dfs(root);cout << min(f[root][1], f[root][0]) << endl;}return 0;
}

Acwing 1077. 皇宮看守

太平王世子事件后，陸小鳳成了皇上特聘的御前一品侍衛。

皇宮以午門為起點，直到后宮嬪妃們的寢宮，呈一棵樹的形狀，某些宮殿間可以互相望見。

大內保衛森嚴，三步一崗，五步一哨，每個宮殿都要有人全天候看守，在不同的宮殿安排看守所需的費用不同。

可是陸小鳳手上的經費不足，無論如何也沒法在每個宮殿都安置留守侍衛。

幫助陸小鳳布置侍衛，在看守全部宮殿的前提下，使得花費的經費最少。

輸入格式

輸入中數據描述一棵樹，描述如下：

第一行$n$，表示樹中結點的數目。

第二行至第$n+1$行，每行描述每個宮殿結點信息，依次為：該宮殿結點標號為$i$，在該宮殿內安置侍衛所需的經費$k$，該邊的兒子數$m$，接下來$m$個數，分別是這個結點的$m$個兒子的編號$r_1,r_2,?,r_m$

對于一個$n$個節點的樹，結點標號在$1$到$n$之間，且標號不重復。

輸出格式

輸出最少的經費。

數據范圍

$0<N\le 1500$

思路

在這題中，同樣是挑選足夠的點完成整顆樹的覆蓋，但是對于每條邊來說，這一題的狀態表示與之前并不一樣，使用$f[i][0]$表示點$i$被父節點看到的最小花費，$f[i][1]$表示點$i$被子節點看到的最小花費，$f[i][2]$表示點$i$上擺放守衛的最小花費。

對于狀態轉移，當節點狀態為$f[i][0]$時，那么他的最小花費就是他的所有子節點狀態為$1$或$2$時的和，但是他的子節點不可能是$0$，因為$i$是$0$，表示沒有放侍衛，就不可能看到他的子節點，所以他的子節點只能是另外兩種狀態；當節點狀態為$f[i][2]$時，它的子節點可以是三種狀態，因為它上面放了侍衛；當節點狀態為$f[i][1]$時，表示他是被子節點看到的，因此需要枚舉是哪個子節點看到的它，然后取最小值就行，假設是$k$這個結點看到了$i$，那么一定要有$f[k][2]$，其他的子節點可以是$1$和$2$。

代碼

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;const int N = 1510;int n;
int f[N][3];
int h[N], e[N], w[N], ne[N], idx;
bool st[N];void add(int a, int b)
{e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}void dfs(int u)
{f[u][2] = w[u];for(int i = h[u]; i != -1; i = ne[i]){int j = e[i];dfs(j);f[u][0] += min(f[j][1], f[j][2]);f[u][2] += min(f[j][0], min(f[j][1], f[j][2]));}f[u][1] = 1e9;for(int i = h[u]; i != -1; i = ne[i]){int j = e[i]; // 枚舉是哪個子節點看到當前節點uf[u][1] = min(f[u][1], f[j][2] + f[u][0] - min(f[j][1], f[j][2]));}
}int main()
{cin >> n;memset(h, -1, sizeof h);for(int i = 1; i <= n; i ++){int id, cnt, cost;cin >> id >> cost >> cnt;w[id] = cost;while(cnt --){int ver;cin >> ver;add(id, ver);st[ver] = true;}}int root =  1;while(st[root]) root ++;dfs(root);cout << min(f[root][1], f[root][2]) << endl;return 0;
}