状压 DP:f[点集][叶子集] 统计恰含 k 个叶子的生成树,靠「每次只剥离编号最小的叶子」保证每棵树恰被计一次。
OJ: roj
题目 ID: 1781
难度:提高
标签:动态规划状态压缩生成树python
创建: 2026-10-08 02:18
更新: 2026-10-08 02:18
形式化题目
给定一张
注意题面里"树相同"说的是画法(摆放、旋转)不算区别,同一棵树的两种画法仍是同一棵。
因此这里的"树"是图论意义上的点集+边集:只要边集不同就是不同的树,不需要做树同构判重。
样例可以印证:
正解
思路
最直接的做法是枚举边集:从
一棵树里,点和边的关系可以拆成两层:
- 设叶子集合为
( ),非叶子集合为 。把 中的点和 与它们相连的边全部删掉,剩下的 在原树里仍是一棵连通树( |M| >= 2时), 记为;而 中每个点在原树里只有一条边,连向 中某个点。 - 于是"叶子集恰为
的生成树"与下面这组数据一一对应: 在原图里的导出子图 上的一棵生成树 ,加上给 中每个点选定的那个 -邻居。
一一对应关系立刻带来一条约束:
到这里方向清楚了:枚举
不过"枚举
删掉一棵树的任意叶子,剩下的仍是一棵树,且新树只在这一个叶子的邻居处度数减一。
于是规定:每次只剥离"当前树中编号最小的叶子"。设当前叶子集为
| 旧树的叶子集 | |
|---|---|
反过来写就是转移方程(mask 中、且不在叶子集里的邻居):
因为"剥最小叶子"这道手续给定一棵树后剥离序列唯一(每一步被剥的点由状态自己决定, 没有选择余地),所以每棵树恰被统计一次。
边界:两个点的树(一条边)里两个点都是叶子,不满足上面的"
一行伪代码式的流程:
for mask 从小到大: # 去掉一个点后点集必更小,顺序天然正确
若 |mask| = 2: 有一条边则 f[mask][mask] = 1; 跳过
for leaf 是 mask 的子集:
j = lowbit(leaf); rest = mask 去 j; old = leaf 去 j
for k in mask 且 k 不在 leaf 且 (j,k) 有边:
f[mask][leaf] += f[rest][old] + f[rest][old | (1<<k)]
答案 = Σ_{|leaf| = k} f[full][leaf]状态数
代码
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-08 02:18
# update_at: 2026-10-08 02:18
import sys
from collections import defaultdict
type Adj = list[list[int]] # 邻接矩阵,1 表示有边
type Dp = list[defaultdict[int, int]] # dp[点集][叶子集] = 树的棵数
def lowbit_index(mask: int) -> int:
"""最低位 1 的下标(0-based),即「编号最小的元素」。"""
return (mask & -mask).bit_length() - 1
def count_death_trees(n: int, adj: Adj, leaves: int) -> int:
"""统计恰含 leaves 个叶子的带标号生成树棵数。
dp[mask][leaf] = 点集 mask、叶子集恰为 leaf 的树棵数。
去重靠一条唯一性:规定每次剥离「当前树中编号最小的叶子」j = lowbit(leaf),
j 在树中的唯一邻居 k 必不是叶子(k ∉ leaf),剥掉 j 后叶子集只会
「不变」(k 原非叶子)或「多出 k」(k 原为叶子),故递推唯一、无重无漏。
"""
full = (1 << n) - 1
dp: Dp = [defaultdict(int) for _ in range(full + 1)]
for mask in range(1, full + 1):
if bin(mask).count("1") == 2:
# base:恰一条边,两点都是叶子
x = lowbit_index(mask)
y = lowbit_index(mask ^ (1 << x))
if adj[x][y]:
dp[mask][mask] = 1
continue
leaf = mask
while leaf: # 枚举 mask 的所有子集当叶子集
j = lowbit_index(leaf) # 最后被剥离的点
rest, old = mask ^ (1 << j), leaf ^ (1 << j)
for k in range(n):
kb = 1 << k
# k 是 j 在旧树里的唯一邻居:在 mask 内、不是叶子、且与 j 有边
k_can_be_parent = mask & kb and not leaf & kb and adj[j][k]
if k_can_be_parent:
dp[mask][leaf] += dp[rest][old] + dp[rest][old | kb]
leaf = (leaf - 1) & mask
return sum(cnt for leaf, cnt in dp[full].items() if bin(leaf).count("1") == leaves)
def solve() -> None:
data = iter(map(int, sys.stdin.buffer.read().split()))
n, m, leaf_count = next(data), next(data), next(data)
adj: Adj = [[0] * n for _ in range(n)]
for _ in range(m):
a, b = next(data) - 1, next(data) - 1
adj[a][b] = adj[b][a] = 1
print(count_death_trees(n, adj, leaf_count))
if __name__ == "__main__":
solve()/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-10-08 02:18
* update_at: 2026-10-08 02:18
*/
// 死亡之树:统计图 G 中恰含 k 个叶子(度数为 1)的带标号生成树棵数
// n <= 10, m <= 45,状压 DP:f[点集][叶子集]
//
// 不重不漏的关键:一棵树若有 >= 3 个点,就有 >= 2 个叶子。规定每次只剥离
// 「当前树中编号最小的叶子」 j(即 j = leaf 的最低位),那么 j 的剥离位置唯一:
// j 在树中的唯一邻居 k 必须不是叶子(k ∈ mask \ leaf),剥掉 j 得到小一圈的树。
// 反向就得到递推:叶子集不再变(k 原非叶子)或把 k 补进叶子集(k 原为叶子)。
// 每棵树的剥离序列唯一,所以每个状态恰好被统计一次。
//
// 两点情形(一条边)里两个点都是叶子,不满足「k 不是叶子」,单独作为 base。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 10; // 点数上限
const int MAXM = 1 << MAXN;
int n, m, K;
int adj[MAXN][MAXN]; // 邻接矩阵,1 表示有边(题面保证无重边、无自环)
ll f[MAXM][MAXM]; // f[点集][叶子集]:点集内部、叶子集恰为该集合的树棵数
int main() {
scanf("%d %d %d", &n, &m, &K);
for (int i = 1; i <= m; i++) {
int a, b;
scanf("%d %d", &a, &b);
a--; b--; // 转 0-based
adj[a][b] = adj[b][a] = 1;
}
int full = (1 << n) - 1;
// 按点集大小顺序递推:mask 去掉一个点后必然更小,故 mask 从小到大即可
for (int mask = 1; mask <= full; mask++) {
if (__builtin_popcount(mask) == 2) {
// base:恰两个点,有边则构成一棵树,两点都是叶子
int x = __builtin_ctz(mask);
int y = __builtin_ctz(mask ^ (1 << x));
if (adj[x][y]) f[mask][mask] = 1;
continue;
}
// 枚举叶子集 leaf,必须是 mask 的子集
for (int leaf = mask; leaf; leaf = (leaf - 1) & mask) {
int j = __builtin_ctz(leaf); // 编号最小的叶子 = 最后被加入的点
int jb = 1 << j;
int rest = mask ^ jb; // 剥掉 j 后的点集
int oldLeaf = leaf ^ jb; // 情形 (a):k 在原树里度数 >= 2,叶子集不变
// 枚举 j 在原树中的唯一邻居 k:k 必须在 mask 里且不是叶子
for (int k = 0; k < n; k++) {
int kb = 1 << k;
if (!(mask & kb) || (leaf & kb)) continue;
if (!adj[j][k]) continue;
f[mask][leaf] += f[rest][oldLeaf] // (a) k 原非叶子
+ f[rest][oldLeaf | kb]; // (b) k 原为叶子,补进叶子集
}
}
}
ll ans = 0;
for (int leaf = 1; leaf <= full; leaf++)
if (__builtin_popcount(leaf) == K) ans += f[full][leaf];
printf("%lld\n", ans);
return 0;
}复杂度
时间 long long 的
总结
本题是"树上叶子计数"这类问题的状压 DP 模板:把"树的叶子集"当作状态的一维,
用
另一条可选的路线是"枚举叶子集
说明
本题目素材来自公开题面重建(题面文字与「一本通·高手训练」系列的《死亡之树》一致),
data/ 目录含数据生成脚本 data.py,属自造数据:10 个测试点覆盖最小规模(.out 逐一比对通过,但与官方原题
的测试数据不保证一致,请以本篇题面的模型为准。