死亡之树

GitHub跳转原题关系图返回列表

状压 DP:f[点集][叶子集] 统计恰含 k 个叶子的生成树,靠「每次只剥离编号最小的叶子」保证每棵树恰被计一次。

OJ: roj

题目 ID: 1781

难度:提高

标签:动态规划状态压缩生成树python

创建: 2026-10-08 02:18

更新: 2026-10-08 02:18

形式化题目

给定一张 nn 个点、mm 条边的无向简单图(无重边、无自环),点数 n⩽10n \leqslant 10。 求图中有多少棵生成树恰好含 kk 个叶子,其中"叶子"指度数为 11 的节点:

答案=#{ T:T 是 G 的生成树,  ∣{v∈V:deg⁡Tv=1}∣=k }.\text{答案} = \#\{\,T : T \text{ 是 } G \text{ 的生成树},\; |\{v \in V : \deg_T v = 1\}| = k\,\}.

注意题面里"树相同"说的是画法(摆放、旋转)不算区别,同一棵树的两种画法仍是同一棵。 因此这里的"树"是图论意义上的点集+边集:只要边集不同就是不同的树,不需要做树同构判重。 样例可以印证:K3K_3 里 k=2k = 2 的生成树是 33 条路径,K4K_4 里 k=3k = 3 的生成树是 44 个星形, 都是按标号、按边集计数的结果。

正解

思路

最直接的做法是枚举边集:从 mm 条边里选 n−1n - 1 条,再用并查集判断连通、统计度数。 但 mm 最大到 45=(102)45 = \binom{10}{2},(459)≈8.9×108\binom{45}{9} \approx 8.9 \times 10^8,必然超时。 换一个枚举对象才是正路:枚举每个点的"角色"——它是不是叶子。

一棵树里,点和边的关系可以拆成两层:

  • 设叶子集合为 LL(∣L∣=k|L| = k),非叶子集合为 M=V∖LM = V \setminus L。把 LL 中的点和 与它们相连的边全部删掉,剩下的 MM 在原树里仍是一棵连通树(|M| >= 2 时), 记为 TMT_M;而 LL 中每个点在原树里只有一条边,连向 MM 中某个点。
  • 于是"叶子集恰为 LL 的生成树"与下面这组数据一一对应:MM 在原图里的导出子图 上的一棵生成树 TMT_M,加上给 LL 中每个点选定的那个 MM-邻居。

一一对应关系立刻带来一条约束:MM 中的点 uu 在原树里的度数等于 “uu 在 TMT_M 里的度数”+“选它当父亲的叶子个数”。若 uu 在 TMT_M 里度数 ⩾2\geqslant 2 就自动合格;只有当 uu 是 TMT_M 的叶子时,才必须至少被一个叶子点选中。

到这里方向清楚了:枚举 LL((nk)⩽(105)=252\binom{n}{k} \leqslant \binom{10}{5} = 252 种), 枚举 TMT_M,然后数"每个 MM-叶至少被选一次"的选法数。后者用容斥: 对 TMT_M 的叶子集 AA 的子集 SS 强制"禁止连向 SS 里的点",被禁的点从各叶子的 可选邻居里去只掉,方案数是 ∏v∈L∣ Γ(v)∩M∖S ∣\prod_{v \in L}\bigl|\,\Gamma(v) \cap M \setminus S\,\bigr|。

不过"枚举 LL 再枚举 TMT_M"要写两重嵌套的生成树搜索,代码偏长。有一个更紧凑的等价形态, 直接把两层合成一个状压 DP:f[点集][叶子集]f[\text{点集}][\text{叶子集}]。 DP 的难点在去重——同一棵树会被多种"组装顺序"生成。破局点是一条简单但关键的性质:

删掉一棵树的任意叶子,剩下的仍是一棵树,且新树只在这一个叶子的邻居处度数减一。

于是规定:每次只剥离"当前树中编号最小的叶子"。设当前叶子集为 LL,j=lowbit(L)j = \mathrm{lowbit}(L) (编号最小的叶子),它是最后被加进来的点,在树中的唯一邻居记作 kk。 由 jj 是叶子可知 k∉Lk \notin L(kk 在原树里度数 ⩾2\geqslant 2)。剥掉 jj 后得到小一圈的树:

kk 在旧树里的度数 旧树的叶子集
⩾2\geqslant 2 L∖{j}L \setminus \{j\},叶子集不变
=1= 1(kk 原是叶子) (L∖{j})∪{k}(L \setminus \{j\}) \cup \{k\},kk 度数升到 2,不再是叶子

反过来写就是转移方程(kk 取遍 jj 在 mask 中、且不在叶子集里的邻居):

f[mask][L]=∑k(f[mask∖j][L∖j]+f[mask∖j][(L∖j)∪{k}]).f[\text{mask}][L] = \sum_{k} \Bigl( f[\text{mask} \setminus j][L \setminus j] + f[\text{mask} \setminus j][(L \setminus j) \cup \{k\}] \Bigr).

因为"剥最小叶子"这道手续给定一棵树后剥离序列唯一(每一步被剥的点由状态自己决定, 没有选择余地),所以每棵树恰被统计一次。

边界:两个点的树(一条边)里两个点都是叶子,不满足上面的"k∉Lk \notin L"前提, 作为 base 单独置 f[{x,y}][{x,y}]=1f[\{x,y\}][\{x,y\}] = 1(x,yx,y 相邻时)。 另外 n=1n = 1 或答案要求的叶子数超出可行范围(如 n⩾2n \geqslant 2 时 k<2k < 2、 k=nk = n)时没有合法树,DP 自然给出 00,无需特判。

一行伪代码式的流程:

text
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]

状态数 2n×2n2^n \times 2^n 只有 10610^6,转移里挑 kk 是 O(n)O(n),总量在 10610^6 量级, n⩽10n \leqslant 10 时运行时间不到 10 ms10\ \text{ms}。

代码

python
#!/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()
cpp
/**
 * 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;
}

复杂度

时间 O(n⋅3n)O(n \cdot 3^n)(枚举 (mask,leaf)(\text{mask}, \text{leaf}) 对共 3n3^n 组,每组挑 kk 花 O(n)O(n)), n=10n = 10 时约 6×1056 \times 10^5 次运算;空间 O(4n)O(4^n),即两个 long long 的 210×2102^{10} \times 2^{10} 数组,约 8 MB8\ \text{MB},远低于 256 MB 限制。

总结

本题是"树上叶子计数"这类问题的状压 DP 模板:把"树的叶子集"当作状态的一维, 用 f[点集][叶子集]f[\text{点集}][\text{叶子集}] 描述连通块结构。 真正值得记住的不是转移式本身,而是去重手法——"每次只剥离编号最小的叶子"让每棵树 对应唯一的剥离序列,于是不需要任何树同构判重或集合级去重,答案就是各状态的直接求和。 这也印证了题面的"树相同"指的是画法而非结构:若是结构同构计数,n⩽10n \leqslant 10 的小数据下 仍需上树同构算法,与样例的答案也对不上。

另一条可选的路线是"枚举叶子集 →\to 枚举内部生成树 →\to 容斥补叶子度数",两者复杂度 同阶、思路互为镜像;DP 写法的优势是内层循环天然把两条路合并了,代码短且没有递归搜索。

说明

本题目素材来自公开题面重建(题面文字与「一本通·高手训练」系列的《死亡之树》一致), data/ 目录含数据生成脚本 data.py,属自造数据:10 个测试点覆盖最小规模(n=2n=2)、 不连通(答案 00)、题面两个样例、以及顶格 K10K_{10} 的两个闭式答案(k=9k=9 星形 1010 棵、 k=2k=2 哈密顿路 10!/2=181440010!/2 = 1814400 棵)。结论与生成的 .out 逐一比对通过,但与官方原题 的测试数据不保证一致,请以本篇题面的模型为准。