先用一元生成函数统计普通子树的剪枝顺序，再在 1 到 x 的路径上做带“前后分配”的树形计数 DP。
OJ: luogu
题目 ID: P8935
难度:省选/NOI-
标签:动态规划树形DP组合计数计数
日期: 2026-06-21 10:41
题意
有一棵以 1 为根的树，每次可以选一个还没有被删掉的点 u，删掉它整棵子树。
一旦删掉 1，整个过程立刻结束。
现在指定了根到 x 的这条路径是“茎”，要求：
- 第
k次操作必须主动选择x - 在第
k次及以前，不能通过删除x的祖先，把x连带删掉
问满足条件的操作序列有多少种，答案对 10^9+7 取模。
思路
先看一个可以直接验证想法的朴素解：
cpp
#include <bits/stdc++.h>
using namespace std;
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
const long long MOD = 1000000007LL;
int n, k, x;
vector<int> g[25];
vector<int> child[25];
int parent_node[25];
int tin[25], tout[25], timer_cnt;
unordered_map<unsigned long long, long long> memo;
void dfs_build(int u, int fa) {
parent_node[u] = fa;
tin[u] = ++timer_cnt;
for (int v : g[u]) {
if (v == fa) {
continue;
}
child[u].push_back(v);
dfs_build(v, u);
}
tout[u] = timer_cnt;
}
bool in_subtree(int u, int v) {
return tin[u] <= tin[v] && tin[v] <= tout[u];
}
// mask 表示当前还活着的点集合，step 表示当前是第几次操作。
long long dfs(long long mask, int step) {
if (((mask >> 0) & 1LL) == 0) {
return step - 1 >= k ? 1 : 0;
}
unsigned long long key = (unsigned long long) mask * 32ULL + (unsigned long long) step;
unordered_map<unsigned long long, long long>::iterator it = memo.find(key);
if (it != memo.end()) {
return it->second;
}
long long ans = 0;
for (int u = 1; u <= n; u++) {
if (((mask >> (u - 1)) & 1LL) == 0) {
continue;
}
// x 只能在第 k 次被主动选择。
if ((u == x) != (step == k)) {
continue;
}
// 在第 k 次及以前，不能删掉 x 的祖先来连带剪掉 x。
if (step <= k && u != x && in_subtree(u, x)) {
continue;
}
long long new_mask = mask;
for (int v = 1; v <= n; v++) {
if (((mask >> (v - 1)) & 1LL) == 0) {
continue;
}
if (in_subtree(u, v)) {
new_mask &= ~(1LL << (v - 1));
}
}
ans += dfs(new_mask, step + 1);
if (ans >= MOD) {
ans %= MOD;
}
}
ans %= MOD;
memo[key] = ans;
return ans;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> k >> x;
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs_build(1, 0);
memo.clear();
long long full_mask = (1LL << n) - 1;
cout << dfs(full_mask, 1) % MOD << '\n';
return 0;
}暴力的做法很直接：把当前还活着的点集记下来，每次枚举下一步删哪个点，只要不违反“第 k 次必须删 x”和“第 k 次前不能删 x 的祖先”这两个限制，就继续递归。
这个方法能帮助我们把题意看清楚，但显然只能跑很小的数据。
真正的难点在于：不同子树里的操作可以互相穿插，直接做树形 DP 很容易把“穿插方案数”漏掉。
这里可以先把普通子树单独拿出来。
设 F_u(t) 表示在 u 的整棵子树里，恰好做 t 次操作的方案数，再把它改写成指数型生成函数的形式：
A_u(z) = sum(F_u(t) / t! * z^t)
这样一来，不同儿子子树之间的“任意穿插”就会自动变成普通乘法。
对于一个普通点 u：
- 如果最后不删
u，那就是把所有儿子子树各自处理完 - 如果最后删
u，那就是先处理完所有儿子子树，再补一刀删u
于是就能得到一元 DP。
递推公式：普通子树
设所有儿子的 EGF 乘积为：
如果不主动删除 u，贡献是 P_u(z)；如果最后补一刀删除 u，在 EGF 中相当于积分一次。
因此：
这正对应代码里 res[t] += prod[t] 与 res[t+1] += prod[t] / (t+1)。
接下来只剩下路径 1 -> x 需要特殊处理。
路径外的侧枝有一个很重要的性质：
- 它们的操作既可以放在
x前面，也可以放在x后面 - 但是路径上的祖先如果被主动删除，那一定只能放在
x后面
所以我们把路径 DP 压成两类数量：
a：一定在x前面 的操作数s：来自侧枝、可以自由分到x前后 的操作数
为了继续保留“任意穿插”的信息，代码里不是直接存普通方案数，而是存基底 p^a (p+q)^s 下的系数。
这样做的好处是：
- 侧枝合并时，只会把
s增加，等价于乘一个一元多项式 - 某个祖先
u被删除时，这一步一定发生在x之后，对应对变量q做一次积分
这里最关键的式子是：
∫ p^a (p+q)^s dq = (p^a (p+q)^(s+1) - p^(a+s+1)) / (s+1)
也就是说，删祖先以后：
- 一部分贡献会进入
p^a (p+q)^(s+1) - 另一部分要减到
p^(a+s+1)
这就是代码里会出现“加一项、再减一项”的原因。
当我们一路推到根 1 以后，设当前状态是 (a, s)：
a个操作一定在x前面s个侧枝操作里，要再挑出k-1-a个放到x前面
于是最终答案就是把这些“前后分配”的组合数再乘回去：
- 选哪些侧枝放前面：
C(s, k-1-a) - 前面的操作内部任意排列：
(k-1)! - 后面的操作内部任意排列：
(s-(k-1-a))!
整个过程本质上就是：
- 普通子树做一元生成函数计数
- 茎上做一个带前后分配的树形计数 DP
- 最后把第
k次落在x的限制还原回来
代码
cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 505;
const int MOD = 1000000007;
int n, k, x;
vector<int> g[MAXN];
vector<int> child[MAXN];
vector<int> order_nodes;
vector<int> path_nodes;
vector<int> poly_all[MAXN]; // 普通子树的一元 EGF：系数 = 方案数 / t!
int parent_node[MAXN];
int stem_next[MAXN];
int inv_num[MAXN], fact[MAXN], comb_num[MAXN][MAXN];
int cur_all[MAXN][MAXN];
int open_dp[MAXN][MAXN];
int next_all[MAXN][MAXN];
int next_close[MAXN][MAXN];
int root_close[MAXN][MAXN];
// 模意义下加法。
inline void add_mod(int &x, long long y) {
x = (x + y) % MOD;
}
// 模意义下减法。
inline void sub_mod(int &x, long long y) {
x = (x - y) % MOD;
if (x < 0) {
x += MOD;
}
}
// 建树，并把无根树转成以 1 为根的有根树。
void dfs_build(int u, int fa) {
parent_node[u] = fa;
order_nodes.push_back(u);
for (int v : g[u]) {
if (v == fa) {
continue;
}
child[u].push_back(v);
dfs_build(v, u);
}
}
// 朴素多项式卷积。
vector<int> multiply_poly(const vector<int> &a, const vector<int> &b) {
vector<int> c((int) a.size() + (int) b.size() - 1, 0);
for (int i = 0; i < (int) a.size(); i++) {
if (a[i] == 0) {
continue;
}
for (int j = 0; j < (int) b.size(); j++) {
if (b[j] == 0) {
continue;
}
c[i + j] = (c[i + j] + 1LL * a[i] * b[j]) % MOD;
}
}
return c;
}
// 计算普通子树的一元 EGF。
// poly_all[u][t] 表示：
// 在 u 的整棵子树里，做出恰好 t 次操作的方案数 / t!。
void build_plain_subtree_dp() {
for (int idx = (int) order_nodes.size() - 1; idx >= 0; idx--) {
int u = order_nodes[idx];
vector<int> prod(1, 1);
for (int v : child[u]) {
prod = multiply_poly(prod, poly_all[v]);
}
vector<int> res((int) prod.size() + 1, 0);
for (int t = 0; t < (int) prod.size(); t++) {
// 不操作 u，自身保留。
add_mod(res[t], prod[t]);
// 最后再操作一次 u。
add_mod(res[t + 1], 1LL * prod[t] * inv_num[t + 1]);
}
poly_all[u] = res;
}
}
// 计算路径点 u 的所有侧枝（不含通向 x 的那条儿子）的一元 EGF。
vector<int> build_side_poly(int u) {
vector<int> prod(1, 1);
for (int v : child[u]) {
if (v == stem_next[u]) {
continue;
}
prod = multiply_poly(prod, poly_all[v]);
}
return prod;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> k >> x;
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
inv_num[1] = 1;
for (int i = 2; i <= n + 1; i++) {
inv_num[i] = MOD - 1LL * (MOD / i) * inv_num[MOD % i] % MOD;
}
fact[0] = 1;
for (int i = 1; i <= n; i++) {
fact[i] = 1LL * fact[i - 1] * i % MOD;
}
for (int i = 0; i <= n; i++) {
comb_num[i][0] = comb_num[i][i] = 1;
for (int j = 1; j < i; j++) {
comb_num[i][j] = comb_num[i - 1][j - 1] + comb_num[i - 1][j];
if (comb_num[i][j] >= MOD) {
comb_num[i][j] -= MOD;
}
}
}
dfs_build(1, 0);
build_plain_subtree_dp();
// 找出从 1 到 x 的茎。
int cur = x;
while (cur != 0) {
path_nodes.push_back(cur);
cur = parent_node[cur];
}
reverse(path_nodes.begin(), path_nodes.end());
for (int i = 0; i + 1 < (int) path_nodes.size(); i++) {
stem_next[path_nodes[i]] = path_nodes[i + 1];
}
memset(cur_all, 0, sizeof(cur_all));
memset(root_close, 0, sizeof(root_close));
for (int idx = (int) path_nodes.size() - 1; idx >= 0; idx--) {
int u = path_nodes[idx];
vector<int> side_poly = build_side_poly(u);
if (u == x) {
memset(cur_all, 0, sizeof(cur_all));
for (int a = 0; a < (int) side_poly.size(); a++) {
cur_all[a][0] = side_poly[a];
}
if (u == 1) {
memcpy(root_close, cur_all, sizeof(root_close));
}
continue;
}
memset(open_dp, 0, sizeof(open_dp));
for (int a = 0; a <= n; a++) {
for (int s = 0; s <= n; s++) {
if (cur_all[a][s] == 0) {
continue;
}
int lim = min((int) side_poly.size() - 1, n - s);
for (int r = 0; r <= lim; r++) {
if (side_poly[r] == 0) {
continue;
}
add_mod(open_dp[a][s + r], 1LL * cur_all[a][s] * side_poly[r]);
}
}
}
memset(next_all, 0, sizeof(next_all));
memset(next_close, 0, sizeof(next_close));
for (int a = 0; a <= n; a++) {
for (int s = 0; s <= n; s++) {
next_all[a][s] = open_dp[a][s];
}
}
// 对 q 积分：
// ∫ p^a (p+q)^s dq = (p^a (p+q)^(s+1) - p^(a+s+1)) / (s+1)
for (int a = 0; a <= n; a++) {
for (int s = 0; s <= n; s++) {
int val = open_dp[a][s];
if (val == 0) {
continue;
}
if (s + 1 <= n) {
int add = 1LL * val * inv_num[s + 1] % MOD;
add_mod(next_close[a][s + 1], add);
add_mod(next_all[a][s + 1], add);
if (a + s + 1 <= n) {
sub_mod(next_close[a + s + 1][0], add);
sub_mod(next_all[a + s + 1][0], add);
}
}
}
}
memcpy(cur_all, next_all, sizeof(cur_all));
if (u == 1) {
memcpy(root_close, next_close, sizeof(root_close));
}
}
int need_before = k - 1;
int answer = 0;
for (int a = 0; a <= n; a++) {
for (int s = 0; s <= n; s++) {
int val = root_close[a][s];
if (val < 0) {
val += MOD;
}
if (val == 0) {
continue;
}
int choose_before = need_before - a;
if (choose_before < 0 || choose_before > s) {
continue;
}
int after_cnt = s - choose_before;
long long ways = 1LL * val * comb_num[s][choose_before] % MOD;
ways = ways * fact[need_before] % MOD;
ways = ways * fact[after_cnt] % MOD;
add_mod(answer, ways);
}
}
cout << answer % MOD << '\n';
return 0;
}复杂度
普通子树的一元 DP 总复杂度是
路径上的状态转移本质是若干次多项式卷积，整体复杂度为
空间复杂度是
总结
这题最难的地方不是“树”，而是“不同子树的操作顺序如何穿插”。
一旦用指数型生成函数把穿插方案数吸收进去，再把茎上的操作拆成：
- 必须在
x前面的 - 可以自由分配到
x前后的
整个计数结构就清楚了。关键在于祖先删除那一步对应的是“对后缀变量积分”，这一步想通以后，状态转移就会非常顺。
一图流解析
这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。
