XCPC wiki - 树 02 - 树形 DP | 小明の雜貨鋪

在树上，我们可以任选一个节点作为根节点，从而定义出每个节点的深度和每棵子树的根。

在 DP 的状态表示中，第一维通常是节点编号，第二维代表状态基。大多数时候，我们采用递归的方式实现树形动态规划。对于每一个节点 $x$ ，先递归它的每一个子节点上进行 DP ，在 回溯时，从子节点向节点 $x$ 进行状态转移。

有根树的树形 DP

树背包

有根树，有点权。 $m$ 元点集 $S$ 满足：若子节点 $\in S$ ，则父节点 $\in S$ 。最大化 $S$ 点权和。

int n, m, w[N], dp[N][M];
auto dfs = [&](this auto&& dfs, int u) -> void {
    dp[u][1] = w[u];
    for (auto& v : E[u]) {
        dfs(v);
        for (int k = m; k >= 1; --k) {
            for (int i = k; i <= m; i++)
                dp[u][i] = max(dp[u][i], dp[u][k] + dp[v][i - k]);  // i>=k
        }
    }
};
printf(dp[st][m]);

最大子树点权和

有根树，有点权。最大化子树点权和。

int n, w[N], dp[N];
int ans = -0x3f3f3f3f;
auto dfs = [&](this auto&& dfs, int u) -> void {
    dp[u] = w[u];
    for (auto& v : E[u]) {
        dfs(v);
        dp[u] = max(dp[u] + dp[v], dp[u]);
    }
    ans = max(ans, dp[u]);
};
print(ans);

无根树的树形 DP

可 任选一点为根，尝试将问题化为子树上的问题。

最大独立集

无根树，点集 $S$ 满足： $S$ 中任意两个点没有直接相连的边。最大化 $S$ 点权和。

可任选一点为根，则点集 $S$ 满足若父节点 $\in S$ ，则子节点 $\not\in S$ 。

状态表示：
设 $f[u,j]$ 表示选完第 $u$ 个节点以及它所有的子树的方案
其中 $j=0$ 表示第 $u$ 个节点不选， $j=1$ 表示第 $u$ 个节点选择
属性：点权和的最大值

状态转移：
设 $v$ 为 $u$ 的子节点

若 $j=0$ ，那么它的子节点可选可不选，即 $f[u,0] = f[u,0]+\max\{f[v,0],f[v,1]\}$
若 $j=1$ ，那么它的子节点只能不选，即 $f[u,1]=f[u,1]+f[v,0]$

int n, w[N], dp[N][2];
auto dfs = [&](this auto&& dfs, int u) -> void {
    dp[u][1] = w[u];
    for (auto& v : E[u]) {
        dfs(v);
        dp[u][0] += max(dp[v][0], dp[v][1]);
        dp[u][1] += dp[v][0];
    }
};
print(max(dp[rt][0], dp[rt][1]));

最小点覆盖

树。点集 $S$ 满足：对于树的每一条边 $E_{uv}$ ，有 $u\in S \lor v\in S$ 。最小化 $S$ 的元素数量。

int n, dp[N][2];
auto dfs = [&](this auto&& dfs, int u) -> void {
    dp[u][0] = 0, dp[u][1] = 1;
    for (auto v : E[u]) {
        dfs(v);
        dp[u][0] += dp[v][1];
        dp[u][1] += min(dp[v][1], dp[v][0]);
    }
};
print(min(dp[rt][0], dp[rt][1]));

子图个数

无根树。求包含 $u$ 的子图个数。

Input	Output
6 1 2 1 3 2 4 4 5 4 6	12 15 7 16 9 9

vector<int> E[N];
Z f[N];     // u的子树且包含u的子图个数
Z g[N];     // 包含u的子图个数
auto dfs1 = [&](this auto&& dfs, int u, int p) -> void {
    f[u] = 1;
    for (auto& v : E[u]) {
        if (v == p) continue;
        dfs1(v, u);
        f[u] *= f[v] + 1;
    }
}
auto dfs2 = [&](this auto&& dfs, int u, int p) -> void {
    for (auto& v : E[u]) {
        if (v == p) continue;
        g[v] = g[u] / (f[v] + 1) * f[v] + f[v];
        dfs2(v, u);
    }
}

dfs1(1, 0);
g[1] = f[1], dfs2(1, 0);
print(g);

带权染色

题意给树上每个点染色，颜色编号 $c_{i}$ 为正整数，相邻节点不能同色，求 $\sum\limits_{i=1}^{n}a_i c_i$ 的最小值。(The Omnipotent Monster Killer)

思路状态表示： $f_{u,j}$ 表示在节点 $u$ 上的染成颜色 $j$ ，且 $u$ 的子树已经全部染色的方案
属性： $\sum\limits_{i\in \operatorname{subtree(u)}}^{n}a_i c_i$ 的最小值。

状态转移：设 $v$ 为 $u$ 的子节点， $f_{u,j}\leftarrow \sum\min\limits_{k\neq j}\{f_{v,k}\}$

可以发现总操作次数不会很多，因为即使最笨的办法，给未染色的节点二染色，然后选择权值较大的部分染色也可以让未染色的节点数减少一半。所以每次至少可以让未染色的节点的总权值减少一半，总权值数量级 $10^{12}\times3\times10^{5}= 3\times10^{17}$ 。使用不超过 60 种颜色就能染完所有点。

时间复杂度 $\Theta(n\log^{2} v)$ ，其中 $v$ 是点权和。

constexpr int N = 3e5 + 8, K = 60;
vector<int> E[N];
ll w[N], dp[N][K];

auto dfs = [&](this auto&& dfs, int u, int p) -> void {
    for (int i = 1; i < K; i++) dp[u][i] = i * w[u];

    for (auto& v : E[u]) {
        if (v == p) continue;
        dfs(v, u);

        for (int i = 1; i < K; i++) {
            ll mn = 8e18;
            for (int j = 1; j < K; ++j) {
                if (i != j) mn = min(mn, dp[v][j]);
            }
            dp[u][i] += mn;
        }
    }
}

void eachT() {
    // 读入并dfs
    ll ans = 8e18;
    for (int i = 1; i < K; i++) {
        ans = min(ans, dp[1][i]);
    }
    printf("%lld\n", ans);
}

前后缀和最小值优化 时间复杂度 $\Theta(n\log v)$ ，其中 $v$ 是点权和。

constexpr int N = 3e5 + 8, K = 60;
vector<int> E[N];
ll w[N], dp[N][K];
ll pre[N], suf[N];

auto dfs = [&](this auto&& dfs, int u, int p) -> void {
    for (int i = 1; i < K; i++) dp[u][i] = i * w[u];
    pre[0] = 1e18, suf[K] = 1e18;

    for (auto& v : E[u]) {
        if (v == p) continue;
        dfs(v, u);

        for (int i = 1; i < K; i++) pre[i] = min(dp[v][i], pre[i - 1]);
        for (int i = K - 1; i; --i) suf[i] = min(dp[v][i], suf[i + 1]);

        for (int i = 1; i < K; i++) {
            dp[u][i] += min(pre[i - 1], suf[i + 1]);
        }
    }
}

状态表示优化 时间复杂度 $\Theta(n\log v)$ ，空间复杂度 $\Theta(n)$ 。

constexpr int N = 3e5 + 8;
vector<int> E[N];
ll w[N];
ll dp1[N], dp2[N];    // 最优解 次优解
int t[N];             // 第几次选是最优的

auto dfs = [&](this auto&& dfs, int u, int p) -> void {
    int cnt = E[u].size() - (p != 0);  // 子节点个数

    ll sum = 0;              // 子节点的最小值之和
    vector<ll> d(cnt + 3);   // 子节点的次小值与最小值之差的和

    for (auto& v : E[u]) {
        if (v == p) continue;
        dfs(v, u);

        sum += dp1[v];
        if (t[v] < cnt + 3) {
            d[t[v]] += dp2[v] - dp1[v];  // 第t[v]次选是最优的 如果第t[v]次不选v 差值是dp2[v]-dp1[v]
        }
    }

    for (int i = 1; i <= cnt + 2; i++) {  // 枚举第i次选u 这里循环到+2而不是+1是因为要更新次小值
        ll res = sum + d[i] + i * w[u];
        if (res < dp1[u]) {  // 更新最小值
            dp2[u] = dp1[u];
            dp1[u] = res;
            t[u] = i;
        }
        else if (res < dp2[u]) {  // 更新次小值
            dp2[u] = res;
        }
    }
}

void eachT() {
    // 读入并dfs
    printf("%lld\n", dp1[1]);
}

连通导出子图的 MEX 之和

给定一棵 $n$ 个点的树，点权为排列。求这棵树的所有连通导出子图的 MEX 之和。([[…/contests/2024杭电多校/2024-08-05：2024“钉耙编程”中国大学生算法设计超级联赛（6）|2024-08-05：2024“钉耙编程”中国大学生算法设计超级联赛（6）]])

int n;
cin >> n;
vector<int> w(n), p(n), vis(n);
for (int i = 0; i < n; i++) {
    cin >> w[i];
}
for (int i = 1; i < n; i++) {
    int u = w[read()], v = w[read()];
    E[u].push_back(v);
    E[v].push_back(u);
}
vector<Z> f(n);   // u的子树且包含u的子图个数
auto dfs = [&](this auto&& dfs, int u) -> void {
    f[u] = 1;
    for (auto& v : E[u]) {
        if (v == p[u]) continue;
        p[v] = u;
        dfs(v);
        f[u] *= f[v] + 1;
    }
};
dfs(0);
vis[0] = 1;
Z res = f[0], sum = res;
for (int i = 2; i <= n; i++) {
    int u = i;
    if (!vis[u]) {
        vector<int> stk;
        while (!vis[u]) {
            stk.push_back(u);
            u = p[u];
        }
        while (!stk.empty()) {
            int v = stk.back(); stk.pop_back();
            sum = sum / (f[v] + 1) * f[v];
            vis[v] = 1;
        }
    }
    res += sum;
};
cout << res << '\n';

拓扑序计数

引理（拓扑序计数）给定一棵树，在点上写一个排列，使得每个点的点权比其父亲的数大的方案数，这等价于，满足每个节点的父亲排在他前面的排列方案数为 $\dfrac{n!}{\prod_{i=0}^{n-1} s_{i}}$ 。

题意求满足 $p_{i}=i$ 的拓扑序计数。数据范围： $n \leqslant 5000$ 。([[…/contests/2024-11-03-2024 ICPC 南京|2024-11-03-2024 ICPC 南京]])

思路树形 DP，常见的 $f_{p_{u}}\leftarrow f_{u}$ 不易转移，考虑从外而内地 DP，也就是 $f_{u}\leftarrow f_{p_{u}}$ 。值得注意的是，为避免后效性，这里的设 $f_{u}$ 表示处理除去 $u$ 子树以外的其它节点的状态。

对于本题，设键 $f_{u,i}$ 表示处理除去 $u$ 子树以外的其它节点，且 在 $\pmb{u}$ 处填 $\pmb{i}$ ，值是 方案数。

思考如何转移 $f_{u}\leftarrow f_{p_{u}}$ ，对于本题是 $f_{u,j}\leftarrow f_{p_{u},i}$ ，也就是 $p_{u}$ 填 $i$ ， $u$ 填 $j$ ，需要同时处理在 $p_{u}$ 子树而不在 $u$ 子树的其它节点。

两个问题：哪些位置？什么顺序？

空位：由于 $u$ 子树的节点必须放在 $u$ 后面，所以 $u$ 后面至少要留 $s_{u}-1$ 个给子树，其余位置可以填，所以选择的方案数是 $\operatorname{C}_{n-j-1}^{s_{u-1}}$ 。这不是转移系数，因为如果已经钦定 $u$ 子树中节点的位置，DP 就有后效性了。再回看转移目标，需要 $p_{u}$ 后面至少要留 $s_{p_{u}}-1$ 个给子树，除去 $u$ 子树中 $s_{u}$ 那些节点，现在需要钦定的只有 $s_{p_{u}}-1-s_{u}$ 个节点，因此选择的方案数是 $a=\operatorname{C}_{n-i-1-s_{u}}^{s_{p_{u}}-1-s_{u}}$ 。
顺序：需要计算 $u$ 所有兄弟节点的子树拓扑序方案数，根据上面的引理， $v$ 子树的拓扑序计数是 $\dfrac{s_{v}!}{\prod_{i\in s_{v}} s_{i}}$ ，因此所需方案数是
$b=\prod_{v}\dfrac{s_{v}!}{\prod_{i\in s_{v}} s_{i}}=\dfrac{(s_{p_{u}}-s_{u})!}{\big(\prod_{i\in s_{p_{u}}} s_{i}\big)/\big(\prod_{i\in s_{u}} s_{i}\big)}$

这两个式子相乘 $ab$ 就是转移系数。这样的转移是 $\Theta(n^{2})$ 的，不难用前缀和优化到 $\Theta(n)$ 。

现在得到的不是答案，因为 $f_{u,i}$ 还没有考虑 $u$ 的子树。

空位：需要钦定 $u$ 子树所有节点的位置，所以方案数就是刚才提到的 $c=\operatorname{C}_{n-i-1}^{s_{u-1}}$
顺序：即是 $u$ 子树的拓扑序 $d=\dfrac{s_{u}!}{\prod_{i\in s_{u}} s_{i}}$ 。

所以拓扑序中 $u$ 填 $i$ 的方案数 $g_{u,i}=cdf_{u,i}$ ，这就是所求。

总的时空复杂度 $\Theta(n^{2})$ 。

（没用取模类，代码很丑）

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

constexpr int mod = 998244353;
constexpr int N = 5e3 + 8;
ll fac[N], ifac[N];

ll qpow(ll a, ll n) {
	ll res = 1;
	while (n) {
		if (n & 1) res = res * a % mod;
		a = a * a % mod;
		n >>= 1;
	}
	return res;
}

ll inv(ll n) {
	return qpow(n, mod - 2);
}

void init(int n) {
	fac[0] = ifac[0] = 1;
	for (int i = 1; i <= n; i++) {
		fac[i] = fac[i - 1] * i % mod;
	}
	ifac[n] = inv(fac[n]);
	for (int i = n; i > 0; i--) {
		ifac[i - 1] = ifac[i] * i % mod;
	}
}

ll C(int n, int m) {
	if (n < m || m < 0) return 0;
	return fac[n] * ifac[m] % mod * ifac[n - m] % mod;
}

int main() {
	int n;
	cin >> n;

	init(n);

	vector p(n, -1); 
	for (int i = 1; i < n; i++) {
		cin >> p[i];
		p[i]--;
	}

	vector siz(n, 1LL); // 子树大小
	for (int i = n - 1; i; i--) {
		siz[p[i]] += siz[i];
	}

	auto psiz = siz;  // 子树的siz之积 prod-siz
	for (int i = n - 1; i; i--) {
		psiz[p[i]] *= psiz[i];
		psiz[p[i]] %= mod;
	}

	vector dp(n, vector<ll>(n));
	dp[0][0] = 1;
	for (int i = 1; i < n; i++) {
		vector<ll> pre(n);
		for (int j = 0; j < n - 1; j++) {
			ll tmp = dp[p[i]][j] * C(n - 1 - j - siz[i], siz[p[i]] - 1 - siz[i]) % mod;
			(pre[j + 1] += pre[j] + tmp) %= mod;
		}
		ll tmp = fac[siz[p[i]] - siz[i] - 1] * inv(psiz[p[i]]) % mod * psiz[i] % mod * siz[p[i]] % mod;
		for (int j = 1; j < n; j++) {
			(dp[i][j] += pre[j] * tmp) %= mod;
		}
	}

	for (int i = 0; i < n; i++) {
		cout << (dp[i][i] * C(n - 1 - i, siz[i] - 1) % mod * fac[siz[i]] % mod * inv(psiz[i]) % mod) << " \n"[i == n - 1];
	}

	return 0;
}

爆 LL 的剪枝技巧

2024 杭电多校 7009 - 关于 agKc 实在不喜欢自动化于是啥都自己合成这件事

[[…/contests/2024杭电多校/2024-08-05：2024“钉耙编程”中国大学生算法设计超级联赛（7）|2024-08-05：2024“钉耙编程”中国大学生算法设计超级联赛（7）]]

方程为 $f_{u}=\sum w_{uv}f_{v}$ ，题目要求若 $f_{1}>10^{9}$ ，返回 -1，因此将所有 $>10^{9}$ 的 $f$ 视为 $10^{9}+1$ 。

初始化要在 eachT 的最开始而不是最后，因为提前 return 会错过初始化。

ll mx = 0;
vector<vector<pair<ll, int>>> E(n);
vector<ll> f(n);
auto dfs = [&](this auto&& dfs, int u) -> void {
    for (auto& [w, v] : E[u]) {
        dfs(v);
        f[u] += w * f[v];
        if (f[u] >= INF) {
            f[u] = INF;
            break;
        }
    }
};
int ok = 1;
for (auto& [w, v] : E[rt]) {
    dfs(v);
    f[rt] += w * f[v];
    mx = max(mx, w * f[v]);
    if (f[rt] - mx > INF) {
        ok = 0;
        break;
    }
};
if (ok) printf("%lld\n", ww[rt] - mx);
else printf("Impossible\n");

换根 DP

树。求一个节点，使得以这个节点为根时，所有节点的深度之和最大。

vector<int> siz(n), dep(n), dp(n);
auto dfs = [&](this auto&& dfs, int u, int p) -> void {
    siz[u] = 1;
    dp[u] = dep[u] = dep[p] + 1;
    for (auto v : E[u]) {
        if (v == p) continue;
        dfs(v, u);
        siz[u] += siz[v];
        dp[u] += dp[v];
    }
};
dfs(0, -1);
int imx = 0;
auto dfs2 = [&](this auto&& dfs, int u, int p) -> void {
    for (auto v : E[u]) {
        if (v == p) continue;
        dp[v] = dp[u] - (siz[v]) + (n - siz[v]);
        dfs2(v, u);
    }
    if (dp[u] >= dp[imx]) imx = u;
};
dfs2(0, -1);
print(imx);

求以每个点为根时树的高度，这用换根 DP 可以在 $\Theta(n)$ 的时间内求得。

点 $u$ 为根时树的高度 $= \max(u$ 向下的最长路, $u$ 向上的最长路 $)$ ；
点 $u$ 向下的最长路 $= \max(u$ 子树的向下的最长路 $)+1$ ；
如果点 $u$ 是父亲的长儿子时， $u$ 向上的最长路 $= \max(u$ 的父亲向上的最长路, 父亲向下的次长路 $)+1$ ，否则， $u$ 向上的最长路 $=$ 父亲的深度 $+1$ 。

vector<int> p(n, -1), up(n), d(n), d2(n), id(n, -1);
auto dfs1 = [&](this auto&& dfs, int u) -> void {
    d[u] = 1;
    for (auto v : E[u]) {
        if (v == p[u]) continue;
        p[v] = u;
        dfs(v);
        if (d[v] + 1 >= d[u]) {
            d2[u] = d[u];
            d[u] = d[v] + 1;
            id[u] = v;
        } else if (d[v] + 1 >= d2[u]) {
            d2[u] = d[v] + 1;
        }
    }
};
dfs1(0);

vector<int> dp(n);
auto dfs2 = [&](this auto&& dfs, int u) -> void {
    for (auto v : E[u]) {
        if (v == p[u]) continue;
        if (v == id[u]) {
            up[v] = max(up[u] + 1, d2[u] + 1);
        } else {
            up[v] = dp[u] + 1;
        }
        dp[v] = max(d[v], up[v]);
        dfs(v);
    }
};
dp[0] = d[0];
dfs2(0);