题解：Bi-ing Lottery Tickets

题目分析

问题核心

给定一棵有 (N) 个节点的有根二叉树（根为节点 (1)）和 (K) 个球，每个球有指定投放节点。球按某种顺序投放，遵循特定移动规则停留在树中节点，需计算所有可能的“中奖彩票”数量（即球最终停留位置的不同组合数），结果对 (10^9+7) 取模。

关键规则与约束

1. 投放冲突：若投放节点已被占据，球无法投放，无对应中奖彩票。
2. 球的移动规则：
   • 若当前节点无空子女或无子女，球停留。
   • 若只有一个空子女，球移动到该子女。
   • 若有两个空子女：刚投放时可左/右选择；否则沿之前方向移动。
3. 中奖彩票定义：数组第 (i) 位为节点 (i) 停留的球编号（无则为 (0)），不同停留组合即为不同彩票。

数据范围与挑战

• (N, K \leq 4000)，需设计 (O(NK^2)) 或更优复杂度的动态规划算法。
• 核心难点：需同时考虑球的投放顺序、移动路径选择、节点占用冲突，以及所有合法组合的计数。

算法设计

核心思路

将问题转化为树形动态规划（DP），按树的后序遍历处理每个节点，统计该节点子树中“容纳指定数量的球”的合法方案数。关键观察：

1. 每个节点的子树可独立处理（移动规则仅依赖当前节点及子女状态）。
2. 球的投放顺序和移动选择可转化为“组合数+排列数”的计数模型，避免枚举所有可能顺序。
3. 定义状态时需区分“节点可分配的空位数”和“需容纳的球数”，确保无冲突投放。

关键定义

1. 辅助数组：

   • (a[i])：指定投放节点为 (i) 的球的数量。
   • (l[i], r[i])：节点 (i) 的左、右子女（(0) 表示无）。
   • (siz[i])：节点 (i) 为根的子树总节点数。
   • (cnt[i])：节点 (i) 子树中“已被投放球占用”的节点数（含投放节点和停留节点），即 (cnt[i] = cnt[l[i]] + cnt[r[i]] + a[i])。
   • (b[i])：节点 (i) 子树中“空闲节点数”，即 (b[i] = siz[i] - cnt[i])（可用于容纳其他球的移动停留）。

2. DP状态定义：

   • (f[i][j])：以节点 (i) 为根的子树中，额外占用 (j) 个空闲节点（即从 (b[i]) 中使用 (j) 个）时，所有球合法投放并停留的方案数。
   • 目标答案：(f[1][0])（整棵树无额外占用空闲节点，所有球均合法投放）。

动态规划转移（树形后序遍历）

对每个节点 (i)，按左、右子女处理完毕后，合并子女的DP结果，计算当前节点的方案数。转移核心是“分配投放节点为 (i) 的球到左/右子树，并统计组合与排列数”。

转移细节

设节点 (i) 的左子女为 (lc)、右子女为 (rc)，投放节点为 (i) 的球数为 (a[i])：

1. 枚举额外占用数：枚举当前节点需额外占用的空闲节点数 (j)（(0 \leq j \leq b[i]) 且 (j \leq K - cnt[i])，确保总球数不超限）。
2. 分配球到子女：枚举分配到“优先方向子女”（(to)，由父节点移动方向决定）的球数 (k)（(0 \leq k \leq b[to] \cap k \leq a[i])）。
3. 计算组合与排列数：
   • 组合数 (C(a[i], k))：从 (a[i]) 个球中选 (k) 个分配到 (to) 子女。
   • 排列数 (A(k + y, k))：(k) 个球在 (to) 子女的 (k + y) 个节点中排列（(y) 为额外占用数）。
   • 合并子女方案数：(f[to][k + y] \times f[ano][a[i] - k + j - y - flag])（(ano) 为另一子女，(flag) 标记是否占用当前节点）。

预处理

• 阶乘 (fac[i]) 和逆阶乘 (inv[i])：用于快速计算组合数 (C(n, m) = \frac{fac[n]}{fac[m] \cdot fac[n - m]} \mod (10^9+7)) 和排列数 (A(n, m) = \frac{fac[n]}{fac[n - m]} \mod (10^9+7))。
• 快速幂 (qpow)：计算逆阶乘（费马小定理，因 (10^9+7) 为质数）。

代码关键模块解析

1. 预处理模块

const int N = 4e3 + 10, mod = 1e9 + 7;
int qpow(int a, int b) { /* 快速幂计算 a^b mod mod */ }
int fac[N], inv[N];
int C(int n, int m) { /* 组合数 C(n,m) */ }
int A(int n, int m) { /* 排列数 A(n,m) */ }

• 阶乘预处理：(fac[0] = 1)，(fac[i] = fac[i-1] \times i \mod mod)。
• 逆阶乘预处理：(inv[i] = qpow(fac[i], mod - 2) \mod mod)（费马小定理）。

2. 树形DP核心（后序遍历）

void dfs(int i, bool lr) {
    int lc = l[i], rc = r[i];
    if (lc) dfs(lc, 1); // 递归处理左子女
    if (rc) dfs(rc, 0); // 递归处理右子女
    // 计算当前节点的siz、cnt、b
    siz[i] = siz[lc] + siz[rc] + 1;
    cnt[i] = cnt[lc] + cnt[rc] + a[i];
    b[i] = siz[i] - cnt[i];
    // 枚举额外占用的空闲节点数j
    for (int j = 0; j <= b[i] && j <= kk - cnt[i]; j++) {
        int to = (lr ? lc : rc), ano = (lr ? rc : lc);
        // 枚举分配到优先子女to的球数k
        for (int k = 0; k <= b[to] && k <= a[i]; k++) {
            int y = min(j, b[to] - k);
            int flag = (j == b[i]); // 是否占用当前节点
            // 计算排列数与方案数乘积
            int ta = f[to][k + y] * A(k + y, k) % mod;
            int tb = f[ano][a[i] - k + j - y - flag] * A(a[i] - k + j - y, a[i] - k) % mod;
            // 累加组合数 * 子女方案数 * 排列数
            f[i][j] = (f[i][j] + C(a[i], k) * ta % mod * tb % mod) % mod;
        }
    }
}

• 递归处理子女：先处理左、右子女，确保子树的DP结果已计算。
• 状态转移：通过双重循环枚举分配方式，结合组合数（球的分配选择）和排列数（球的投放顺序），合并子女的合法方案数。

3. 输入处理与初始化

signed main() {
    scanf("%lld%lld", &n, &kk);
    fac[0] = inv[0] = f[0][0] = 1; // 初始化：空节点方案数为1
    for (int i = 1; i <= n; i++) {
        fac[i] = fac[i - 1] * i % mod;
        inv[i] = qpow(fac[i], mod - 2);
    }
    // 读取每个球的投放节点，统计a[i]
    for (int i = 1, x; i <= kk; i++) {
        scanf("%lld", &x), a[x]++;
    }
    // 读取树的结构
    for (int i = 1; i <= n; i++) {
        scanf("%lld%lld", &l[i], &r[i]);
    }
    dfs(1, 0); // 从根节点开始DFS，初始方向为0
    printf("%lld", f[1][0]); // 答案为整棵树无额外占用的方案数
    return 0;
}

• 初始化：(f[0][0] = 1)（空节点无球时方案数为1）。
• 输入处理：统计每个节点的投放球数 (a[i])，读取树的子女结构。
• 结果输出：(f[1][0]) 表示整棵树中所有球合法投放且无额外占用空闲节点的方案数，即中奖彩票总数。

时间复杂度与空间复杂度

• 时间复杂度：(O(NK^2))。每个节点需枚举 (O(K)) 个额外占用数，每个占用数需枚举 (O(K)) 个球分配数，共 (N) 个节点，总复杂度符合 (N, K \leq 4000) 的限制。
• 空间复杂度：(O(NK))。DP数组 (f[N][K]) 存储每个节点的状态，阶乘和逆阶乘数组为 (O(N))，整体空间可接受。

关键结论

1. 树形DP是核心：通过后序遍历将子树问题独立处理，降低问题复杂度。
2. 组合与排列数的应用：将球的分配选择和投放顺序转化为数学计数，避免枚举所有可能顺序，大幅提升效率。
3. 状态定义的巧妙性：(f[i][j]) 同时考虑“需容纳的球数”和“额外占用的空闲节点数”，确保无投放冲突，准确统计合法方案。