引言

關于這個樹形 $DP$ 代碼其實都是那一套，核心還是在于思維上的難度，關鍵是這個思路你能不能想明白，想明白了就非常的簡單，因為代碼幾乎長得都差不多，就是某些地方的改變罷了。剛開始學還是很難的，尤其是這種東西還會跟一些其它的算法混在一起，就很討厭了，所以繼續加油吧！

---

一、沒有上司的舞會

標簽：動態規劃、樹形DP、狀態機模型

思路：這道題其實寫了很多遍了，就是定義一個狀態 $f[i][j],(j=0,1)$ ，代表選/不選當前結點 $i$ 的情況下，整個分支的最大值。那么狀態轉移方程為： $$f[u][0]=f[u][0]+\sum max(f[j][0],f[j][1])$$$$f[u][1]=f[u][1]+\sum f[j][0]$$ 然后就進行遞歸操作即可，本質上還是先遞歸到子節點，然后子節點推出根結點的一個過程。

題目描述：

Ural 大學有 N 名職員，編號為 1～N。他們的關系就像一棵以校長為根的樹，父節點就是子節點的直接上司。每個職員有一個快樂指數，用整數 Hi 給出，其中 1≤i≤N。現在要召開一場周年慶宴會，不過，沒有職員愿意和直接上司一起參會。在滿足這個條件的前提下，主辦方希望邀請一部分職員參會，使得所有參會職員的快樂指數總和最大，求這個最大值。輸入格式
第一行一個整數 N。接下來 N 行，第 i 行表示 i 號職員的快樂指數 Hi。接下來 N?1 行，每行輸入一對整數 L,K，表示 K 是 L 的直接上司。（注意一下，后一個數是前一個數的父節點，不要搞反）。輸出格式
輸出最大的快樂指數。數據范圍
1≤N≤6000,?128≤Hi≤127
輸入樣例：
7
1
1
1
1
1
1
1
1 3
2 3
6 4
7 4
4 5
3 5
輸出樣例：
5

示例代碼：

#include <bits/stdc++.h>using namespace std;typedef long long LL;
typedef pair<int,int> PII;
#define x first
#define y secondconst int N = 6010, M = N, INF = 0x3f3f3f3f;int n, m;
int w[N];
int h[N], e[M], ne[M], idx;
int f[N][2];
bool has_father[N];void add(int a, int b)
{e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}void dfs(int u)
{f[u][1] = w[u];for(int i = h[u]; i != -1; i = ne[i]){int j = e[i];dfs(j);f[u][0] += max(f[j][0], f[j][1]);f[u][1] += f[j][0];}
}int main()
{ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);memset(h, -1, sizeof h);cin >> n;for(int i = 1; i <= n; ++i) cin >> w[i];for(int i = 0; i < n - 1; ++i){int a, b; cin >> a >> b;add(b,a);has_father[a] = true;}int root = 1;while(has_father[root]) root++;dfs(root);cout << max(f[root][0], f[root][1]) << endl;return 0;
}

---

二、樹的重心

標簽：dfs、樹形DP

思路：雖然從代碼上感覺不出來這是個 $DP$ ，但其實 $DP$ 就是用一個狀態表示了很多的狀態就叫做 $DP$ ，這道題就是用了一個 $t$ 代表包括它在內的向下子樹的結點的個數，然后在每個結點中都可以求出這個值，然后求出最大的，然后向上的連通塊的個數拿總的結點數減去分支的總和即可，然后找出最小的最大值即可。這里值得注意的是，沒有告訴父子關系，所以我們得建無向邊，同時要防止向上遞歸回去，這里可以用兩種方式解決，第一種是在參數中傳一個參數，是該結點的父親節點，遍歷分支的時候判斷一下即可，第二種是用一個判重數組，訪問過就不訪問了，這兩種都可以。

題目描述：

給定一顆樹，樹中包含 n 個結點（編號 1～n）和 n?1 條無向邊。請你找到樹的重心，并輸出將重心刪除后，剩余各個連通塊中點數的最大值。重心定義：重心是指樹中的一個結點，如果將這個點刪除后，剩余各個連通塊中點數的最大值最小，那么這個節點被稱為樹的重心。輸入格式
第一行包含整數 n，表示樹的結點數。接下來 n?1 行，每行包含兩個整數 a 和 b，表示點 a 和點 b 之間存在一條邊。輸出格式
輸出一個整數 m，表示將重心刪除后，剩余各個連通塊中點數的最大值。數據范圍
1≤n≤105
輸入樣例
9
1 2
1 7
1 4
2 8
2 5
4 3
3 9
4 6
輸出樣例：
4

示例代碼：

#include <bits/stdc++.h>using namespace std;typedef long long LL;
typedef pair<int,int> PII;
#define x first
#define y secondconst int N = 1e5+10, M = N * 2, INF = 0x3f3f3f3f;int n, m;
int h[N], e[M], ne[M], idx;
bool st[N];
int ans = 2e9;void add(int a, int b)
{e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}int dfs(int u)
{st[u] = true;int sum = 1, size = 0;for(int i = h[u]; i != -1; i = ne[i]){int j = e[i];if(st[j]) continue;int t = dfs(j);sum += t;size = max(size, t);}size = max(size, n - sum);ans = min(ans, size);return sum;
}int main()
{ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);memset(h, -1, sizeof h);cin >> n;for(int i = 0; i < n - 1; ++i){int a, b; cin >> a >> b;add(a,b), add(b,a);}dfs(1);cout << ans << endl;return 0;
}

---

三、樹的最長路徑

標簽：樹的深度優先遍歷、DP、樹形DP、樹的直徑

思路：首先這道題要求的是樹的直徑，這道題跟 大臣的旅費 不同的是該題的權重不相同，且不為正整數。最初的想法就是求最長路，想著拿 $spfa$ 求，只要把判斷 $dist$ 的條件變了就行了，但是發現不對，因為 $spfa$ 會重復經過一個點，這個直徑每個點只會經過一次，然后就是用 $Dijkstra$ 求的話，好像它的性質也不適用于最長路，然后就只能用樹形 $DP$ 來求了。然后就是整體的思路就是遞歸每一個點，遞歸的值為該點向下的最大值，然后我們求出每個點多個分支中的第一、第二大點的和，然后對每個點的值求最值就是所求的答案。之所以說這道題為樹形 $DP$ ，還是因為這個 $t$ 代表著是一個集合的一個最值，這是 $DP$ 的核心。
注意的點：第一、第二大值初始化應為 $0$ ，因為代表著無邊，如果是負的，那就不選該邊，也比它大，所以這個值最小也是 $0$ ，代表著什么邊也不選。并且因為只能向下走，跟上道題不同的是，這次使用的是第二種的判斷方法。又因為不知道父子結點的關系，所以要建無向邊，防止不能遞歸所有的點。

題目描述：

給定一棵樹，樹中包含 n 個結點（編號1~n）和 n?1 條無向邊，每條邊都有一個權值。現在請你找到樹中的一條最長路徑。換句話說，要找到一條路徑，使得使得路徑兩端的點的距離最遠。注意：路徑中可以只包含一個點。輸入格式
第一行包含整數 n。接下來 n?1 行，每行包含三個整數 ai,bi,ci，表示點 ai 和 bi 之間存在一條權值為 ci 的邊。輸出格式
輸出一個整數，表示樹的最長路徑的長度。數據范圍
1≤n≤10000,1≤ai,bi≤n,?105≤ci≤105
輸入樣例：
6
5 1 6
1 4 5
6 3 9
2 6 8
6 1 7
輸出樣例：
22

示例代碼：

#include <bits/stdc++.h>using namespace std;typedef long long LL;
typedef pair<int,int> PII;
#define x first
#define y secondconst int N = 1e4+10, M = N * 2, INF = 0x3f3f3f3f;int n, m;
int h[N], e[M], w[M], ne[M], idx;
int ans = -2e9;void add(int a, int b, int c)
{e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}int dfs(int u, int father)
{int d1 = 0, d2 = 0;  // 最次也是0，沒有路徑for(int i = h[u]; i != -1; i = ne[i]){int j = e[i];if(j == father) continue;int t = dfs(j,u) + w[i];if(t >= d1) d2 = d1, d1 = t;else if(t > d2) d2 = t;	} ans = max(ans, d1 + d2);return d1;
}int main()
{ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);memset(h, -1, sizeof h);cin >> n;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;
}

---

四、樹的中心

標簽：樹的深度優先遍歷、DP、樹形DP、換根DP

思路：這道題其實跟上一道題非常的像，題目要求的就是所有結點到其它結點最近的最遠距離是多少，首先我們可以跟上一道題的思路一樣求出每個點向下走的最遠距離，可以用一個數組存起來，然后就是求其向上走的最遠距離了，然后兩個取最大值，最后每個點取最小的最大值即可。前一個就不說了，就是上一題的思路，然后是求向上走的最大距離，向上走的點要么繼續向上走，要么向下走，向上走就是用父結點來更新子結點，我覺得這時候的上和下就剛好反過來了，因為本來這個結點向下走和從父結點到子結點，然后子結點的向上走就是該連邊加上父節點向下走的距離或者是父節點向上走的距離，只不過如果父結點向下走的最長距離中的結點有子結點，那就用第二長邊即可，詳情見代碼。

題目描述：

給定一棵樹，樹中包含 n 個結點（編號1~n）和 n?1 條無向邊，每條邊都有一個權值。請你在樹中找到一個點，使得該點到樹中其他結點的最遠距離最近。輸入格式
第一行包含整數 n。接下來 n?1 行，每行包含三個整數 ai,bi,ci，表示點 ai 和 bi 之間存在一條權值為 ci 的邊。輸出格式
輸出一個整數，表示所求點到樹中其他結點的最遠距離。數據范圍
1≤n≤10000,1≤ai,bi≤n,1≤ci≤105
輸入樣例：
5 
2 1 1 
3 2 1 
4 3 1 
5 1 1
輸出樣例：
2

示例代碼：

#include <bits/stdc++.h>using namespace std;typedef long long LL;
typedef pair<int,int> PII;
#define x first
#define y secondconst int N = 1e4+10, M = N * 2, INF = 0x3f3f3f3f;int n, m;
int h[N], e[M], w[M], ne[M], idx;
int d1[N], d2[N], p1[N], up[N];
bool is_leaf[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)
{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;p1[u] = j;}else if(d > d2[u]){d2[u] = d;}}if(d1[u] == -INF){d1[u] = d2[u] = 0;is_leaf[u] = true;}return d1[u];
}void dfs_u(int u, int father)
{for(int i = h[u]; i != -1; i = ne[i]){int j = e[i];if(j == father) continue;if(j == p1[u]) 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()
{ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);memset(h, -1, sizeof h);cin >> n;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 = d1[1];for(int i = 2; i <= n; ++i){if(is_leaf[i]) res = min(res, up[i]);else res = min(res, max(d1[i], up[i]));}cout << res << endl;return 0;
}