树形DP专题

树形 DP 专题主要包括但不限于以下方面：

树上倍增
LCA(倍增/tarjan)
树的重心
树的直径
树上差分
树形 DP
换根 DP

可以参考的材料：

【动态规划】树形DP完全详解！ - Koshkaaa

lca

最近公共祖先 - OI Wiki

左程云系列：左程云的个人空间-左程云个人主页-哔哩哔哩视频

引入

树的重心
树的最大权值的独立集
树的最小点覆盖
树的最小支配集
树上背包问题
树的直径

子树大小

给定 $n$ 个节点的树，1 号节点为根节点，求以 $i$ 为根的子树的大小。

Solution：设 $f [i]$ 为以 $i$ 为根的子树的大小，则满足 : $f [i] = \sum f [k] + 1$ ，则一遍 DFS 即可。

void dfs(int u){
	if(u is leaf)f[u] = 1, return
	for (v : g[u]){
		dfs(v)
		f[u] += f[v]
	}
	f[u]++
}

树的重心

树的重心，三种定义：

以某节点为根时，最大子树的节点数最少

以某节点为根时，每颗子树的节点数不超过总结点数的一半

以某节点为根时，所有节点都走向重心的总边数最少

给你一个有 $n$ 个点的树，求树的重心。

Solution：设 $F [i]$ 为为删除 $i$ 号点后最大子树的大小， $f [i]$ 为以 $i$ 为根的子树的大小，则有：

$F [i] = max (n - f [i], max (f [k]))$ ， $k$ 是 $i$ 的子节点。

int ans, idx, f[N];
void dfs(int u, int fa) {
    f[u] = 1;
    int mx = 0;
    for (int v : g[u]) {
        if (v == fa)continue;
        dfs(v, u);
        f[u] += f[v];
        mx = max(mx, f[v]);
    }
    mx = max(mx, n - f[u]);
    if (mx < ans) ans = mx, idx = u;
}

当点有点权的时候，点的总数为 $\sum c_{i}$ ，而不是 $n$

Exercise：

带点权且带点权的树： P2986 Great Cow Gathering G
带边权的树/换根 DP [E - Minimize Sum of Distances

P1352 没有上司的舞会~树形DP引入

有 $n$ 名职员，编号为 $1 \sim n$ ，他们的关系就像一棵以老板为根的树，父节点就是子节点的直接上司。每个职员有一个快乐指数，用整数 $H_{i}$ 给出，现在要召开一场周年庆宴会，不过，没有职员愿意和直接上司一起参会。在满足这个条件的前提下，主办方希望邀请一部分职员参会，使得所有参会职员的快乐指数总和最大，求这个最大值。

Solution:

树的最大权值的独立集

儿子父亲不能同时选

设 $u$ 为 $v$ 的父节点， $f [u] [0]$ 代表不选择该节点能得到的最大值，反之是选择能得到的最大值。
若选择了 $u$ 节点这一层，则下一层都不能选择，反之则下一层可以选择也可以不选择，只要保证最大即可。

$f [u] [0] = \sum max (f [v] [0], f [v] [1]), f [u] [1] = \sum f [v] [0] + H [u]$

void solve() {
    int n;cin >> n;vector<int> a(n + 1), vis(n + 1);
    for (int i = 1;i <= n;i++)cin >> a[i];
    vector<vector<int>>g(n + 1);
    vector<array<int, 2>>f(n + 1);
    auto dfs = [&](auto self, int u)->void {
        f[u][1] = a[u];
        for (int v : g[u]) {
            self(self, v);
            f[u][0] += max(f[v][0], f[v][1]);
            f[u][1] += f[v][0];
        }
        };
    for (int i = 1;i < n;i++) {
        int a, b;cin >> a >> b;g[b].push_back(a);vis[a] = 1;
    }
    int u = 0;
    for (int i = 1;i <= n;i++)if (!vis[i])u = i;
    dfs(dfs, u);
    cout << max(f[u][0], f[u][1]) << '\n';
}

Strategic game - POJ 1463

给你一个有 $n$ 个点的树，每两个点之间至多只有一条边。如果在一个结点上放一个士兵，那他能看守与之相连的边，问最少放多少个兵，才能把所有的边能看守住。

Solution:

树的最小点覆盖: 选中的点能够覆盖所有的边。

这题与没有上司的舞会的区别是这题是儿子父亲必须选且只能选一个

设 $f [i] [0]$ 为不在 $i$ 号节点放士兵， $f [i] [1]$ 为在 $i$ 号节点放士兵。且保证每一条以 $i$ 为根每条边都被看住, 则有：

$f [i] [0] = \sum f [k] [1], f [i] [1] = 1 + \sum min (f [k] [0], f [k] [1])$

void dfs(int u) {
    st[u] = 1;f[u][1] = 1;
    for (v : g[u]) {
        if (st[v]) continue;
        dfs(v);
        f[u][0] += f[v][1];
        f[u][1] += min(f[v][0], f[v][1]);
    }
}
dfs(0);
ans = min(f[0][0], f[0][1]);

P2899 Cell Phone Network G

给你一个有 $n$ 个点的树，每两个点之间至多只有一条边。如果在第 $i$ 个点部署信号塔，就可以让它和所有与它相连的点都收到信号。求最少部署多少个信号塔能让所有点都能收到信号。

Solution:

树的最小支配集: 选中的点能够支配所有没有被选择的点

void dfs(int u) {
    vis[u] = 1;
    f[u][0] = 1;
    int tmp = inf;
    bool flag = 1;
    for (int i = 0;i < g[u].size();++i) {
        int y = g[u][i];
        if (vis[y]) continue;
        dfs(y);
        f[u][2] += min(f[y][1], f[y][0]);
        f[u][0] += min({f[y][0], f[y][1], f[y][2]});
        if (f[y][0] <= f[y][1]) {
            flag = 0;
            f[u][1] += f[y][0];
        } else {
            f[u][1] += f[y][1];
            tmp = min(tmp, f[y][0] - f[y][1]);
        }
    }
    if (flag) f[u][1] += tmp;
}

简化后的代码：

void dfs(int u, int fa = 0) {
    bool f = 0;
    for (v : g[u]) {
        if (v == fa) continue;
        dfs(v, u); f |= vis[v];
    }
    if (!f && !vis[u] && !vis[fa])
        vis[fa] = 1, ans += 1;
}
dfs(1);

但是这段代码不能通过带权的最小支配集：P2458 保安站岗

对于带权的最小支配集：每个点带有一定的权值，仍然求最小支配集。只需将 $f [x] [0]$ 初始化为 $a_{i}$ 即可。

void dfs(int x, int fa = -1) {
    f[x][0] = a[x];
    int tmp = inf;
    bool flag = 1;
    for (int i = 0;i < g[x].size();++i) {
        int y = g[x][i];
        if (y == fa) continue;
        dfs(y, x);
        f[x][0] += min({f[y][0], f[y][1], f[y][2]});
        f[x][2] += min(f[y][1], f[y][0]);
        if (f[y][0] <= f[y][1]) {
            flag = 0;
            f[x][1] += f[y][0];
        } else {
            f[x][1] += f[y][1];
            tmp = min(tmp, f[y][0] - f[y][1]);
        }
    }
    if (flag) f[x][1] += tmp;
}

10153 二叉苹果树~树上背包引入

有一棵二叉苹果树，如果树枝有分叉，一定是分两叉，即没有只有一个儿子的节点。这棵树共 $N$ 个节点，标号 $1$ 至 $N$ ，树根编号一定为 1。

我们用一根树枝两端连接的节点编号描述一根树枝的位置。一棵有四根树枝的苹果树，因为树枝太多了，需要剪枝。但是一些树枝上长有苹果，给定需要保留的树枝数量，求最多能留住多少苹果。

Solution：

树上背包问题

对于本题：

设 $f [i] [j]$ 表示以 $i$ 为根的子树保留 $j$ 个树枝可以得到的最大苹果数量。

设 $a [i] . l | r$ 表示连接 $i$ 和其左|右儿子的树枝上的苹果数量

对于节点 $i$ ：

若左右子树都保留，设左右子树分别保留 $x, y$ 个树枝，以 $i$ 为根的子树保留 $j$ 个树枝，则 $x + y + 2 = j \to y = j - x - 2$ ，则有： $f [i] [j] = max_{x \in [0, j - 2]} (f [l] [x] + f [r] [j - x - 2] + a [j] . l + a [j] . r)$

若只保留左子树，所以左子树保留了 $j - 1$ 个树枝，则有： $f [i] [j] = f [l] [j - 1] + a [j] . l$

若只保留右子树，所有右子树保留了 $j - 1$ 个树枝，则有： $f [i] [j] = f [r] [j - 1] + a [j] . r$

若都不保留，则 $j = 0$ , $f [i] [0] = 0$

$f [u] [i] = max (f [u] [i], f [u] [i - j - 1] + f [v] [j] + w)$

$f [v] [j]$ 代表右子树保留 $j$ 个树枝可以得到的最大苹果数量
$f [u] [i - j - 1]$ 代表左子树保留 $i - j - 1$ 个树枝可以得到的最大苹果数量

void solve() {
    int n, r;cin >> n >> r;
    vector<vector<pair<int, int>>> g(n + 1);
    for (int i = 1;i < n;i++) {
        int u, v, w;cin >> u >> v >> w;
        g[u].push_back({v,w});// g[v].push_back({u,w});
    }
    vector<vector<int>> f(n + 1, vector<int>(n + 1));
    vector<int> siz(n + 1);
    auto dfs = [&](auto self, int u, int fa = 0) ->void {
        siz[u] = 1;
        for (auto [v, w] : g[u]) {
            if (v == fa)continue;
            self(self, v, u);
            siz[u] += siz[v];

            for (int i = min(siz[u], r);i > 0;i--) {
                for (int j = 0;j <= min(siz[v], i - 1);j++) {
                    f[u][i] = max(f[u][i], f[u][i - j - 1] + f[v][j] + w);
                }
            }
        }
        };
    dfs(dfs, 1);
    cout << f[1][r] << '\n';
}

Q：若这个题目说的不是二叉树，而是多叉树如何解决？A：也可以用上面的方法解决。

树上背包问题还有：
P2014 选课：
这个题目的思路与本题相似，代码：

$f [u] [i] [j]$ 表示节点 $u$ 的前 $i$ 个节点，限重为 $j$ 能达到的最大权值和。

状态压缩后得到 $f [u] [j]$

3 维相对 01 背包的两维来说，多了一个体积做变量的一维

void solve() {
    int n, m;cin >> n >> m;
    vector < vector<int>> g(n + 1);
    vector<int> s(n + 1);
    for (int i = 1;i <= n;i++) {
        int f, w;cin >> f >> w;
        g[f].push_back(i);s[i] = w;// g[i].push_back(f);
    }
    vector<int> siz(n + 1);
    vector<vector<int>> f(n + 1, vector<int>(m + 2));
    auto dfs = [&](auto self, int u, int fa = -1) ->void {
        siz[u] = 1;
        f[u][1] = s[u];
        for (auto v : g[u]) {
            if (v == fa)continue;
            self(self, v, u);
            siz[u] += siz[v];
            
			for (int i = min(siz[u], m + 1);i > 0;i--) {
				for (int j = 0;j < i;j++) {
					f[u][i] = max(f[u][i], f[u][i - j] + f[v][j]);
				}
			}
        }
        };
    dfs(dfs, 0);
    cout << f[0][m + 1] << '\n';
}

核心代码也可以替换为：

for (int i = min(siz[u], m + 1);i > 0;i--) {
	for (int j = 1;j <= min(siz[v], m + 1 - i);j++) {
		f[u][i + j] = max(f[u][i + j], f[u][i] + f[v][j]);
	}
}

树的直径

树中所有最短路径的最大值即为树的直径。

性质：

若树上所有边边权均为正，则树的所有直径中点重合
可以有多个直径，这些直径长度都相等
对于树上任意一点，相隔最远的点的集合，必定是直径的一端。

有两种方式求： $O (n)$

两次 DFS (只适用于边为非负边权)：先随便从一个点开始 DFS 找到距离这个点最远的点，这个距离最远的点再进行 DFS，这时的最大值即为直径。(也可以 BFS)

void dfs(int u, int fa) {
    for (int v : g[u]) {
        if (v == fa) continue;
        d[v] = d[u] + 1;
        if (d[v] > d[c]) c = v;
        dfs(v, u);
    }
}
dfs(1, 0);d[c] = 0, dfs(c, 0);
ans -> d[c]

树形 DP：这里例举出来的是默认边权为 1 的树, 若有边权，则将 1 替换为 $w (u, v)$ 即可。

void dfs(int u, int fa) {
  d1[u] = d2[u] = 0;
  for (int v : g[u]) {
    if (v == fa) continue;
    dfs(v, u);
    int t = d1[v] + 1;
    if (t > d1[u])
      d2[u] = d1[u], d1[u] = t;
    else if (t > d2[u])
      d2[u] = t;
  }
  d = max(d, d1[u] + d2[u]);
}
ans -> d

或者：

转移方程： $f [u] = max (d p [u], d p [v] + w (u, v))$

void dfs(int u, int fa) {
  for (int v : g[u]) {
    if (v == fa) continue;
    dfs(v, u);
    d = max(d, dp[u] + dp[v] + 1);
    dp[u] = max(dp[u], dp[v] + 1);
  }
}
ans -> d

Exercise：

深入

树上倍增
LCA(tarjan/倍增)
树上差分
换根 DP
树链剖分

换根 DP

换根 DP 即为树形 DP 的变形。可以通过树的某种性质使得少遍历一个循环 $O (n^{2}) \to O (n)$

算法讲解123【扩展】树上问题专题6-换根dp_哔哩哔哩_bilibili

$f_{v} \leftarrow f_{u}$ 可以体现换根，即以 $u$ 为根转移到以 $v$ 为根。显然在换根的转移过程中，以 $v$ 为根或以 $u$ 为根会导致其子树中的结点的深度产生改变。具体表现为：

所有在 $v$ 的子树上的结点深度都减少了一，那么总深度和就减少了 $s_{v}$ ；

所有不在 $v$ 的子树上的结点深度都增加了一，那么总深度和就增加了 $n - s_{v}$ ；

根据这两个条件就可以推出状态转移方程 $f_{v} = f_{u} - s_{v} + n - s_{v} = f_{u} + n - 2 \times s_{v}$ 。

例题：给定一个 $n$ 个点的树，请求出一个结点，使得以这个结点为根时，所有结点的深度之和最大。

P3478 STA-Station

#define int long long
void solve() {
    int n;cin >> n;
    vector<vector<int>> g(n + 1);
    for (int i = 1;i < n;i++) {
        int u, v;cin >> u >> v;
        g[u].push_back(v);g[v].push_back(u);
    }
    vector<int> siz(n + 1), dep(n + 1);
    auto dfs1 = [&](auto self, int u, int fa = 0) ->void {
        siz[u] = 1;
        dep[u] = dep[fa] + 1;
        for (auto v : g[u]) {
            if (v == fa)continue;
            self(self, v, u);
            siz[u] += siz[v];
        }
        };

    dfs1(dfs1, 1);
    vector<int> f(n + 1);
    for (int i = 1;i <= n;i++)f[1] += dep[i];
    
    auto dfs2 = [&](auto self, int u, int fa = 0) ->void {
        for (auto v : g[u]) {
            if (v == fa)continue;
            f[v] = f[u] + n - 2 * siz[v];
            self(self, v, u);
        }
        };
    dfs2(dfs2, 1);
    int ans = -1, idx = -1;
    for (int i = 1;i <= n;i++) {
        if (f[i] > ans) {
            ans = f[i];
            idx = i;
        }
    }
    cout << idx << '\n';
}

Exercise ：第一道题相对第二道多加入了边权。

带点权且带点权的树： P2986 Great Cow Gathering G

即求： $f (x) = \sum_{i = 1}^{n} (C_{i} \times Distance (x, i)) \to min_{1 \leq x \leq n} f (x)$

luogu 题解：

#define int long long
void solve() {
    int n;cin >> n;
    vector<int>c(n + 1);int tot = 0;
    for (int i = 1;i <= n;i++)cin >> c[i], tot += c[i];
    vector<vector<pair<int, int>>> g(n + 1);
    for (int i = 1;i < n;i++) {
        int u, v, w;cin >> u >> v >> w;
        g[u].push_back({v,w});g[v].push_back({u,w});
    }
    vector<int>dis(n + 1), res(n + 1);
    auto dfs1 = [&](auto self, int u, int fa = -1) ->void {
        res[u] = c[u];
        for (auto [v, w] : g[u]) {
            if (v == fa)continue;
            self(self, v, u);
            res[u] += res[v];
            dis[u] += dis[v] + w * res[v];
        }
        };
    dfs1(dfs1, 1);
    vector<int> f(n + 1);
    auto dfs2 = [&](auto self, int u, int fa = -1) ->void {
        for (auto [v, w] : g[u]) {
            if (v == fa)continue;
            f[v] = f[u] + (tot - 2 * res[v]) * w;
            self(self, v, u);
        }
        };
    dfs2(dfs2, 1);
    int ans = 1e18;
    for (int i = 1;i <= n;i++)ans = min(ans, f[i]);
    cout << ans + dis[1] << '\n';
}

E - Minimize Sum of Distances 根据上面的例子，只需要将 w=1 即可。

TODO: 学习树上差分，树上倍增，然后 LCA (tarjan)

将郑州邀请赛 K：K 树上问题还有 E - Minimize Sum of Distances 补了这部分就暂时告一段落。