把树形限制拆成祖先约束与兄弟链约束,按后序遍历自底向上做树形 DP,倒序合并兄弟子树,用组合数 C(N_i-1, sz_i-1) 统计跨子树插空。
OJ: roj
题目 ID: 1772
难度:提高
标签:树形DP组合数学python
创建: 2026-10-08 01:36
更新: 2026-10-08 01:36
形式化题目
给出
- 祖先限制:若
是 的后继(子孙),则 必须排在 之前; - 兄弟限制:设
的孩子按喜爱度从大到小为 (即输入顺序), 则必须满足 排在 之前、 排在 之前……即 。
求合法排列的数量
注意「
输入格式:第一行
题面样例:
(
正解
思路
朴素做法。 把树边和兄弟链边当成一般 DAG,枚举全排列逐一检验,
瓶颈在哪? 状压爆炸的根源是「必须把已排好的节点集合原样记住」。但本题的约束是 分层给出的:祖先限制只关心「谁是谁的祖先」,兄弟限制只关心「同一父亲的孩子们谁先谁后」。 约束既然能按子树分解,就应当按子树聚合——这正是树形 DP 的形状。
设
= 子树 的节点数; = 只考虑子树 内部的节点,满足「祖先在前」与「兄弟按序」的排列个数。
关键观察一:每个子树内部自成序列,且子树根必在首位。 由祖先限制,
关键观察二:不同子树之间的约束只有「根谁先谁后」。 兄弟限制
于是可以倒序合并。设已经合并好
- 由观察二,
与右侧所有元素无约束;由观察一, 在 中最靠前; 又由兄弟限制 , 是右侧那段的首元素——三者合起来, 在 这段并集中, 必定占据第一位; - 而
一旦占了首位,剩下的 个 内节点与右侧 个节点之间 再无任何交叉约束,可以任意交错插空:先在 个位置里挑 个位置 放右侧那段(放法即 ),然后两段各自按合法顺序填入。
所以合并一步就是
从
换一种写法:记
为什么必须倒序? 因为「
实现细节。
- 自底向上:用迭代后序遍历(
的链会爆递归栈),得到一个「孩子必在父亲之前」 的序列,正序扫描即为自底向上。 - 组合数:
是质数且 ,阶乘预处理 + 费马小定理求逆元即可, 不需要 Lucas,分母恒不为 。 - 多组数据记得清空每个点的孩子表(本实现用
vector的clear()逐点重置)。 时没有孩子, ,DP 自动兼容。
代码
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++ 正式解:
/**
* 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;
}复杂度
- 时间:阶乘预处理
;每组数据后序遍历 ,每次合并 ,合并总数 ,故每组 ,总计 。 时运算量在 量级, ms 时限绰绰有余。 - 空间:孩子表、
f、sz、阶乘数组各,总计 。
总结
这道题的关键不是「树形 DP」这四个字,而是看清跨子树之间到底还剩什么约束:
祖先限制被「子树根必在首位」吸收掉,兄弟限制在并集里退化成「
反过来,如果兄弟限制被换成「
数据来源说明:本题素材目录里带有生产数据的
data.py,说明个测试点是 自造的(分层覆盖 、 、题面样例、 、 、 的 随机树 / 深链 / 完全二叉树 / 菊花,以及 、 的多组点), 题面文本为网络重建,与官方原题的出题意图可能存在偏差;本文所有结论均以题面 + 该批 数据的实测结果为准。