Skip to content

樹 DP

在樹上 DP，通常會使用 DFS（遞迴），從父節點遞迴到子節點，再合併子節點的答案。

最小點覆蓋

給定一棵樹 ，樹上所有點一開始為白色，要求將一些點塗成黑色，使得所有的邊至少與一個黑色點相連，求最少要塗幾個點？

  • 狀態： 代表以 為根的子樹，在點 為 (0: 白色；1: 黑色），最小需要幾個點為黑色。

  • 初始狀態：如果 是葉節點， 。

  • 轉移

    • 當 為白色， 的子節點應為黑色
    • 當 為黑色， 的子節點可為白色或黑色
最大獨立集 / AtCoder Educational DP Contest P

給定一棵樹 ，樹上所有點一開始為白色，要求將一些點塗成黑色，任兩個相鄰點不能皆為黑色，問有幾種塗法。

  • 狀態： 代表以 為根的子樹，在點 為 ( 0: 白色；1: 黑色），合法的塗法數。
  • 初始狀態：如果 是葉節點， 。
  • 轉移
    • 當 為白色， 的子節點應為白色或黑色：
    • 當 為黑色， 的子節點可為白色：

換根 DP（全方位樹 DP)

進行兩次 DFS，第一次求子節點對當前節點的貢獻（樹 DP)，第二次：根據求父節點點對當前節點的貢獻。

樹直徑

樹直徑

一棵樹中，最長的路徑稱為樹直徑。給定一顆樹，求直徑長度。

第一種做法是枚舉所有的點為根，求出兩顆深度最深的子樹 ，找出最大的 ，一次 DFS 的時間複雜度為 ，整體時間複雜度 。

第二種做法是用換根 DP。第一次 DFS 固定一點為根，求出每個點最深的兩顆子樹高度 ( )。第二次 DFS 對於每個點 ，求出經過父節點最長的路徑 ( )。取 前兩大數值和再加 即為答案。這種作法使用了兩次 DFS，時間複雜度 

 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
#include <bits/stdc++.h>
using namespace std;
const int MXV = 15;
vector<int> G[MXV];
int high[MXV][2];
int ans[MXV], height[MXV];

void dfs(int u)
{
    height[u] = 1;
    for (int v : G[u])
    {
        dfs(v);
        height[u] = max(height[u], height[v] + 1);
        if (high[u][0] == 0 || height[high[u][0]] < height[v])
        {
            high[u][1] = high[u][0];
            high[u][0] = v;
        }
        else if (high[u][1] == 0 || height[high[u][1]] < height[v])
        {
            high[u][1] = v;
        }
    }
}

void dfs2(int u, int legnth)
{
    ans[u] = height[high[u][0]] + max(height[high[u][1]], legnth) + 1;
    for (int v : G[u])
    {
        if (v == high[u][0])
        {
            dfs2(v, max(height[high[u][1]], legnth) + 1);
        }
        else
        {
            dfs2(v, max(height[high[u][0]], legnth) + 1);
        }
    }
}

int main()
{
    int n;
    cin >> n;
    for (int i = 1; i < n; ++i)
    {
        int x, y;
        cin >> x >> y;
        G[x].emplace_back(y);
    }
    dfs(1);
    dfs2(1, 0);
    for (int i = 1; i <= n; ++i)
    {
        cout << ans[i] << '\n';
    }
}
AtCoder Educational DP Contest V - Subtree

給定一棵樹 ，樹上所有點一開始為白色，要求將一些點塗成黑色，滿足任兩個黑點之間沒有白點。對於任意點 ，輸出點 塗黑點的方法數。

第一次 DFS 做樹 DP。

  • 狀態： 點 為黑色，所有子樹的塗法數。
  • 轉移：。

第二次 DFS 計算父親 對點 貢獻，將所有 的不所有子樹但包含點 的答案相乘 ()，用迴圈掃描所有子樹一次需要 ， 個子樹需要 ，會超過時間限制；取模數不一定是質數，不能用模逆元；利用前綴積和後綴積，分別代表為 前 顆子樹答案乘積以及 前 顆子樹答案乘積，求出前綴積和後綴積的時間複雜度是 ，計算 的時間複雜度為 。

DAG DP

將點當成狀態，邊當成轉移方向，實作從拓譜排序延伸，時間複雜度為 。

DAG 上最長路徑 / AtCoder Educational DP Contest G

給定一顆有向無環圖，求出圖上最長的路徑。

狀態轉移式如下：

  • 狀態： : 終點為 的情況下，路徑長度最長為何？
  • 初始狀態：
  • 轉移：

答案為 。

例題練習

  • 最近更新:
  • 本文貢獻者: allem40306,