动漫排序

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

把树形限制拆成祖先约束与兄弟链约束,按后序遍历自底向上做树形 DP,倒序合并兄弟子树,用组合数 C(N_i-1, sz_i-1) 统计跨子树插空。

OJ: roj

题目 ID: 1772

难度:提高

标签:树形DP组合数学python

创建: 2026-10-08 01:36

更新: 2026-10-08 01:36

形式化题目

给出 NN 部动漫。除 11 号外,每部动漫有且仅有一部「前传」(父亲),于是 NN 部动漫构成 一棵以 11 号为根的树。一个「排序方案」就是 1∼N1 \sim N 的一个排列 pp,要求

  1. 祖先限制:若 vv 是 uu 的后继(子孙),则 uu 必须排在 vv 之前;
  2. 兄弟限制:设 uu 的孩子按喜爱度从大到小为 c1,c2,…,ckc_1, c_2, \dots, c_k(即输入顺序), 则必须满足 c1c_1 排在 c2c_2 之前、c2c_2 排在 c3c_3 之前……即 c1≺c2≺⋯≺ckc_1 \prec c_2 \prec \cdots \prec c_k。

求合法排列的数量  mod 10007\bmod 10007。

注意「uu 排在子孙之前」与「孩子按序出现」都只是偏序,并不要求某个子树整体连续。 把树边和孩子之间的链式边合起来看,这是一张 DAG,求它的拓扑序个数——一般 DAG 的拓扑序计数 是 #P 完全的,状压 DP 需要 O(2nn)O(2^n n),n=1000n = 1000 时完全不可行。但本题的 DAG 有特殊形状: 除了树边,只有同一个父亲的孩子之间的链式边,这正好容许一个 O(n)O(n) 的树形 DP。

输入格式:第一行 TT(数据组数);每组第一行 nn;接下来 nn 行,第 ii 行先是 tottot, 再是 tottot 个编号,按喜爱度从大到小给出 ii 号动漫的续集。输出每组一行答案。

题面样例:n=5n = 5,11 的孩子是 (4,3,2)(4, 3, 2),33 的孩子是 (5)(5),其余为叶子,答案为 22。 两个合法排列分别是

1,4,3,5,2与1,4,3,2,5.1,4,3,5,2 \qquad \text{与} \qquad 1,4,3,2,5 .

(11 必须最先(它是全树祖先);然后是 4,34, 3 的先后固定;55 是 33 的孩子、必须紧跟 33 之后;而 22 与 55 之间没有任何约束,可前可后——答案恰好是 22。)

正解

思路

朴素做法。 把树边和兄弟链边当成一般 DAG,枚举全排列逐一检验,O(n!⋅n)O(n! \cdot n); 或状压 DP,O(2nn)O(2^n n)。前者只能跑 n≤10n \le 10,后者只能跑 n≤20n \le 20。

瓶颈在哪? 状压爆炸的根源是「必须把已排好的节点集合原样记住」。但本题的约束是 分层给出的:祖先限制只关心「谁是谁的祖先」,兄弟限制只关心「同一父亲的孩子们谁先谁后」。 约束既然能按子树分解,就应当按子树聚合——这正是树形 DP 的形状。

设

  • szusz_u = 子树 T(u)T(u) 的节点数;
  • fuf_u = 只考虑子树 T(u)T(u) 内部的节点,满足「祖先在前」与「兄弟按序」的排列个数。

关键观察一:每个子树内部自成序列,且子树根必在首位。 由祖先限制,uu 必须排在 T(u)T(u) 的所有节点之前,所以 T(u)T(u) 的合法排列一定长成 (u,σ)(u, \sigma),其中 σ\sigma 是 T(u)∖{u}T(u) \setminus \{u\} 的合法排列。

关键观察二:不同子树之间的约束只有「根谁先谁后」。 兄弟限制 ci≺ci+1c_i \prec c_{i+1} 只约束这两个根节点的先后,没有约束 T(ci)T(c_i) 中 cic_i 的子孙与 T(ci+1)T(c_{i+1}) 中元素的先后。 把若干子树的合法序列拼成一段长序列时,唯一新增的约束就是「各子树首元素的出现先后」。

于是可以倒序合并。设已经合并好 ci+1,…,ckc_{i+1}, \dots, c_k,得到一段长度 R=∑j>iszcjR = \sum_{j>i} sz_{c_j} 的合法序列,方案数 WW。现在要并入 T(ci)T(c_i):

  • 由观察二,cic_i 与右侧所有元素无约束;由观察一,cic_i 在 T(ci)T(c_i) 中最靠前; 又由兄弟限制 ci≺ci+1c_i \prec c_{i+1},ci+1c_{i+1} 是右侧那段的首元素——三者合起来, 在 T(ci)∪⋃j>iT(cj)T(c_i) \cup \bigcup_{j>i} T(c_j) 这段并集中,cic_i 必定占据第一位;
  • 而 cic_i 一旦占了首位,剩下的 szci−1sz_{c_i} - 1 个 T(ci)T(c_i) 内节点与右侧 RR 个节点之间 再无任何交叉约束,可以任意交错插空:先在 R+szci−1R + sz_{c_i} - 1 个位置里挑 RR 个位置 放右侧那段(放法即 (R+szci−1R)\binom{R + sz_{c_i} - 1}{R}),然后两段各自按合法顺序填入。

所以合并一步就是

W←W⋅fci⋅(R+szci−1R),R←R+szci,W \leftarrow W \cdot f_{c_i} \cdot \binom{R + sz_{c_i} - 1}{R}, \qquad R \leftarrow R + sz_{c_i},

从 i=ki = k 起(此时 W=fckW = f_{c_k}、R=szckR = sz_{c_k})倒序推到 i=1i = 1,最后令 fu=Wf_u = W、szu=R+1sz_u = R + 1(把 uu 自己算进子树大小)。叶子节点 fu=1f_u = 1、szu=1sz_u = 1。

换一种写法:记 Ni=∑j≥iszcjN_i = \sum_{j \ge i} sz_{c_j},上面的组合数可改写为 (Ni−1szci−1)\binom{N_i - 1}{sz_{c_i} - 1},于是

fu=∏i=1kfci⋅(Ni−1szci−1).f_u = \prod_{i=1}^{k} f_{c_i} \cdot \binom{N_i - 1}{sz_{c_i} - 1}.

为什么必须倒序? 因为「cic_i 占首位」这个结论只在集合是 T(ci)∪T(ci+1)∪⋯∪T(ck)T(c_i) \cup T(c_{i+1}) \cup \cdots \cup T(c_k) 时成立。若正序合并,右侧就不存在 「ci+1c_{i+1} 已经在段内」这个事实,组合数会算多。手算验证样例:f5=1f_5 = 1、sz5=1sz_5 = 1; 节点 33 只有孩子 55,N1=1N_1 = 1,(00)=1\binom{0}{0} = 1,故 f3=1f_3 = 1、sz3=2sz_3 = 2; 节点 11 的孩子依次为 (4,3,2)(4,3,2),从右往左:R=sz2=1R = sz_2 = 1,W=f2=1W = f_2 = 1; 并入 33:(1+2−11)=(21)=2\binom{1 + 2 - 1}{1} = \binom{2}{1} = 2,W=2W = 2、R=3R = 3; 并入 44:(3+1−13)=(33)=1\binom{3 + 1 - 1}{3} = \binom{3}{3} = 1,W=2W = 2。故 f1=2f_1 = 2,与样例一致。

实现细节。

  • 自底向上:用迭代后序遍历(n=1000n = 1000 的链会爆递归栈),得到一个「孩子必在父亲之前」 的序列,正序扫描即为自底向上。
  • 组合数:1000710007 是质数且 n≤1000<10007n \le 1000 < 10007,阶乘预处理 + 费马小定理求逆元即可, 不需要 Lucas,分母恒不为 0(mod10007)0 \pmod{10007}。
  • 多组数据记得清空每个点的孩子表(本实现用 vector 的 clear() 逐点重置)。
  • n=1n = 1 时没有孩子,f1=1f_1 = 1,DP 自动兼容。

代码

Python 短解法(同阶算法,仅常数更大):

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 01:36
# update_at: 2026-10-08 01:36

import sys

MOD = 10007    # 题面模数,是质数且 > n <= 1000,故组合数分母恒不为 0
LIMIT = 1005   # 题面 n <= 1000,留安全余量

type Tree = list[list[int]]  # 孩子的原始顺序(下标 1..n),顺序即喜爱度降序

# 阶乘与其逆元表:供 O(1) 组合数使用,n < MOD 故费马小定理足够、无需求 Lucas
FACT = [1] * LIMIT
for _i in range(1, LIMIT):
    FACT[_i] = FACT[_i - 1] * _i % MOD

INV_FACT = [1] * LIMIT
INV_FACT[LIMIT - 1] = pow(FACT[LIMIT - 1], MOD - 2, MOD)
for _i in range(LIMIT - 1, 0, -1):
    INV_FACT[_i - 1] = INV_FACT[_i] * _i % MOD


def comb(a: int, b: int) -> int:
    """组合数 C(a, b) mod 10007;b 越界时为 0。"""
    if b < 0 or b > a or a < 0:
        return 0
    return FACT[a] * INV_FACT[b] % MOD * INV_FACT[a - b] % MOD


def post_order(tree: Tree, n: int) -> list[int]:
    """以 1 为根的后序遍历序列:孩子一定排在父亲前面,故正序扫描即自底向上。

    迭代实现,避免 n = 1000 的链把递归栈撑爆;stack 顶部正被枚举时,
    直接 pop 掉它的一个孩子当作游标,省掉「每个点已枚举几个孩子」的辅助数组。
    """
    order: list[int] = []
    stack = [1]
    seen = [False] * (n + 1)
    seen[1] = True
    while stack:
        branch = tree[stack[-1]]
        if branch:
            child = branch.pop()
            if not seen[child]:              # 合法输入下恒真,仅防御重复编号
                seen[child] = True
                stack.append(child)
        else:
            order.append(stack.pop())
    return order


def case_answer(tree: Tree, n: int) -> int:
    """一组数据的答案:自底向上树形 DP,返回 f[1]。"""
    f = [1] * (n + 1)    # f[u]:只考虑子树 u 内部节点的合法排列数
    sz = [1] * (n + 1)   # sz[u]:子树 u 的节点数

    kids: Tree = [list(tree[u]) for u in range(n + 1)]  # post_order 会破坏性取用
    for u in post_order(kids, n):
        # 倒序合并:c_i 必占「T(c_i) 及其右侧兄弟子树」的第一位,
        # 余下 sz[c_i]-1 个元素与右侧已合并的 rem 个元素自由插空。
        total = sum(sz[c] for c in tree[u])
        ways, rem = 1, total                # rem = N_i = sum_{j >= i} sz[c_j]
        for c in tree[u]:
            ways = ways * f[c] % MOD * comb(rem - 1, sz[c] - 1) % MOD
            rem -= sz[c]
        sz[u] = total + 1                   # u 自身也要占一位
        f[u] = ways
    return f[1]


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    out: list[str] = []
    T = next(data)

    for _ in range(T):
        n = next(data)
        tree: Tree = [[] for _ in range(n + 1)]
        for u in range(1, n + 1):
            tot = next(data)  # 题面的续集个数
            tree[u] = [next(data) for _ in range(tot)]
        out.append(str(case_answer(tree, n)))

    print('\n'.join(out))


if __name__ == "__main__":
    solve()

C++ 正式解:

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 01:36
 * update_at: 2026-10-08 01:36
 *
 * 一本通 1772《动漫排序》
 *
 * 题意:给出以 1 为根的树,每个点的孩子已按「喜爱度从大到小」列出。
 *   求满足 ① 祖先排在子孙前面;② 同一父亲的孩子们按给定顺序出现的
 *   排列个数,答案 mod 10007(10007 是质数,且 > n)。
 *
 * 算法:树形 DP + 组合数,每组数据 O(n)。
 *   设 f[u] = 子树 u 内部合法的排列数(u 必在子树最前),sz[u] = 子树大小。
 *   u 的孩子依次是 c1..ck(输入顺序即必须满足的先后顺序)。
 *   把「u 在最前,后面接 k 个子树各自合法序列的洗牌」拆开看:
 *   洗牌只额外要求各子树首元素(即 c_i)出现顺序为 c1 < c2 < ... < ck,
 *   与子树内部内容无关,只与各子树长度有关。
 *   记 Cnt(n1..nk) = 长度 n_i 的 k 段序列洗牌、且首元素先后为 1..k 的方案数。
 *   倒着合并:c_i 必定占 T(c_i) 与其后兄弟子树并集的第一个位置,
 *   余下 sz[c_i]-1 个元素与后面已合并的 |U| 个元素自由插空,
 *   于是 Cnt = prod_i C(N_i - 1, sz[c_i] - 1),N_i = sum_{j>=i} sz[c_j],
 *   所以 f[u] = prod_i [ f[c_i] * C(N_i - 1, sz[c_i] - 1) ],答案即 f[1]。
 *
 * 边界:n = 1 时无孩子,f[1] = 1,DP 自然兼容。
 * 数据来源说明:本题 data/ 由随题的 data.py 自造,题面来自网络重建。
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MOD = 10007;
const int MAXN = 1005; // 题面 n <= 1000,留安全余量

ll fact[MAXN];     // 阶乘 mod 10007
ll inv_fact[MAXN]; // 阶乘逆元 mod 10007

vector<int> ch[MAXN]; // 孩子的原始顺序(下标 1..n)
ll f[MAXN];           // f[u]:子树 u 内部的合法排列数 mod 10007
ll sz[MAXN];          // sz[u]:子树 u 的节点数

// 快速幂:模 10007 下的 a^e,用于费马小定理求逆元。
ll mod_pow(ll a, ll e) {
    ll r = 1;
    a %= MOD;
    while (e > 0) {
        if (e & 1) {
            r = r * a % MOD;
        }
        a = a * a % MOD;
        e >>= 1;
    }
    return r;
}

// 组合数 C(a, b) mod 10007;a < 10007 故无需求 Lucas。
ll comb(ll a, ll b) {
    if (b < 0 || b > a || a < 0) {
        return 0;
    }
    return fact[a] * inv_fact[b] % MOD * inv_fact[a - b] % MOD;
}

// 以 1 为根的树做迭代后序遍历,order 中孩子一定排在父亲前面。
void post_order(ll n, vector<int> &order) {
    order.clear();
    vector<int> stk;
    int iter[MAXN]; // 每个点已经枚举过的孩子个数
    bool vis[MAXN];
    for (int i = 1; i <= n; i++) {
        iter[i] = 0;
        vis[i] = false;
    }
    vis[1] = true;
    stk.push_back(1);
    while (!stk.empty()) {
        int u = stk.back();
        if (iter[u] < (int)ch[u].size()) {
            int c = ch[u][iter[u]];
            iter[u]++;
            if (!vis[c]) {
                vis[c] = true;
                stk.push_back(c);
            }
        } else {
            order.push_back(u);
            stk.pop_back();
        }
    }
}

void solve() {
    int T;
    cin >> T;
    while (T--) {
        ll n;
        cin >> n;
        for (int i = 1; i <= n; i++) {
            ch[i].clear();
        }
        for (int i = 1; i <= n; i++) {
            int tot;
            cin >> tot;
            for (int j = 0; j < tot; j++) {
                int x;
                cin >> x;
                ch[i].push_back(x);
            }
        }

        vector<int> order;
        post_order(n, order);

        // order 里孩子先于父亲,顺序处理即为自底向上。
        for (int idx = 0; idx < (int)order.size(); idx++) {
            int u = order[idx];
            ll total = 0; // 所有孩子子树大小之和
            for (int j = 0; j < (int)ch[u].size(); j++) {
                total += sz[ch[u][j]];
            }
            ll res = 1;
            ll rem = total; // N_i:第 i 个孩子及其右侧兄弟的子树大小之和
            for (int j = 0; j < (int)ch[u].size(); j++) {
                int c = ch[u][j];
                res = res * f[c] % MOD;
                res = res * comb(rem - 1, sz[c] - 1) % MOD;
                rem -= sz[c];
            }
            sz[u] = total + 1;
            f[u] = res;
        }
        cout << f[1] % MOD << "\n";
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // 预处理阶乘与逆元:n <= 1000 < MOD,分母不会为 0。
    fact[0] = 1;
    for (int i = 1; i < MAXN; i++) {
        fact[i] = fact[i - 1] * i % MOD;
    }
    inv_fact[MAXN - 1] = mod_pow(fact[MAXN - 1], MOD - 2);
    for (int i = MAXN - 1; i >= 1; i--) {
        inv_fact[i - 1] = inv_fact[i] * i % MOD;
    }

    solve();
    return 0;
}

复杂度

  • 时间:阶乘预处理 O(max⁡n)O(\max n);每组数据后序遍历 O(n)O(n),每次合并 O(1)O(1),合并总数 ∑udeg⁡(u)=n−1\sum_u \deg(u) = n - 1,故每组 O(n)O(n),总计 O(T⋅n)O(T \cdot n)。n=1000n = 1000 时运算量在 10610^6 量级,10001000 ms 时限绰绰有余。
  • 空间:孩子表、f、sz、阶乘数组各 O(n)O(n),总计 O(n)O(n)。

总结

这道题的关键不是「树形 DP」这四个字,而是看清跨子树之间到底还剩什么约束: 祖先限制被「子树根必在首位」吸收掉,兄弟限制在并集里退化成「cic_i 占首位」, 于是剩下的部分完全自由、只剩组合插空。凡是「约束能按子树分层、层间只剩根的先后」的 拓扑序计数题,都可以照这个套路:后序遍历自底向上,倒序合并兄弟子树,组合数统计插空。

反过来,如果兄弟限制被换成「cic_i 的整棵子树都排在 ci+1c_{i+1} 的整棵子树之前」, 那么上面的插空就不再自由、组合数会退化成 11,这也说明了「约束究竟作用在哪些节点上」 是这类题唯一需要盯紧的地方。

数据来源说明:本题素材目录里带有生产数据的 data.py,说明 1010 个测试点是 自造的(分层覆盖 n=1n = 1、n=2n = 2、题面样例、n=10n = 10、n=100n = 100、n=1000n = 1000 的 随机树 / 深链 / 完全二叉树 / 菊花,以及 T=5T = 5、∑n=5000\sum n = 5000 的多组点), 题面文本为网络重建,与官方原题的出题意图可能存在偏差;本文所有结论均以题面 + 该批 数据的实测结果为准。