题目题解

问题理解

给定 $n$ 个顶点的树，根为 $1$。每个顶点 $i$ 有一辆车在时间 $l_i$ 进入根，瞬间移动到 $i$ 并停住，在时间 $r_i$ 原路离开。要求所有 $l_i, r_i$ 构成 $1 \dots 2n$ 的一个排列，且 $l_i < r_i$。
树是有效的，当且仅当所有车辆都能按计划进入和离开，即不存在一辆车在另一辆车经过其路径时仍停在某个顶点上。

目标是：对所有具有 $n$ 个顶点、$k$ 个叶子（根不算叶子）的带标号树，计算上述有效序列对 $(l, r)$ 的总数，对 $998244353$ 取模。

---

单棵树的分析

有效性条件

树有效当且仅当：对于任意顶点 $i$，其子树中所有顶点的 $l$ 和 $r$ 时间区间要么完全包含在 $[l_i, r_i]$ 内，要么与 $[l_i, r_i]$ 不交。
换句话说，$[l_i, r_i]$ 不能包含任何其子树外部顶点的端点。

这等价于：子树中的 $l$ 和 $r$ 必须成对嵌套，且与外部完全分离。

计数公式

通过动态规划或组合分析可得，对于一棵固定的树，有效序列对的数量为

$$\frac{(2n)!}{2^n \cdot s_1 s_2 \cdots s_n},$$

其中 $s_i$ 是以 $i$ 为根的子树大小（包含 $i$）。

---

对所有树求和

我们需要计算

$$\sum_{T \in \mathcal{T}_{n,k}} \frac{(2n)!}{2^n \prod_{i=1}^n s_i}. $$

提取常数因子：

$$\frac{(2n)!}{2^n} \cdot \sum_{T} \frac{1}{\prod_{i=1}^n s_i}. $$

---

转化为拓扑排序计数

已知一个经典结论：一棵树的所有拓扑排序（即满足父节点编号小于子节点的排列）的数量为

$$\frac{n!}{\prod_{i=1}^n s_i}.$$

因此，

$$\frac{1}{\prod s_i} = \frac{\text{拓扑排序数}}{n!}.$$

于是，

$$\sum_{T} \frac{1}{\prod s_i} = \frac{1}{n!} \sum_{T} (\text{拓扑排序数}). $$

---

交换求和顺序

固定一个拓扑排序（即 $1 \dots n$ 的一个排列 $p$，满足如果 $u$ 是 $v$ 的祖先则 $p_u < p_v$），计算有多少棵树以 $1$ 为根且具有该拓扑排序。
这等价于：每个顶点 $i$ 的父节点必须是拓扑序中比它小的某个顶点，且树恰好有 $k$ 个叶子。

---

递推关系

设 $f(n, k)$ 表示 $n$ 个顶点的树（根为 $1$）的拓扑排序数之和（对所有树求和）。
考虑顶点 $n$（最大标号）的位置：

• 若 $n$ 是叶子：则它必须挂在某个编号 $<n$ 的顶点下，且该顶点原本不是叶子（否则会增加叶子数）。
  贡献为 $(n - k) \cdot f(n-1, k-1)$。
• 若 $n$ 不是叶子：则它可挂在任意 $k$ 个叶子之一（因为叶子数不变）。
  贡献为 $k \cdot f(n-1, k)$。

因此：

$$f(n, k) = (n - k) f(n-1, k-1) + k f(n-1, k).$$

边界条件：$f(1, 0) = 1$，$f(1, k) = 0$ for $k \ge 1$。

---

与欧拉数的关系

该递推与欧拉数 $A(n, m)$（计数长度为 $n$ 的排列中恰好有 $m$ 个下降的个数）的递推一致：

$$A(n, m) = (n - m) A(n-1, m-1) + (m+1) A(n-1, m).$$

比较可得：

$$f(n, k) = A(n-1, k-1).$$

其中 $A(n, m)$ 是欧拉数，通常定义为

$$A(n, m) = \sum_{j=0}^{m} (-1)^j \binom{n+1}{j} (m+1-j)^n. $$

---

最终答案

综合以上推导：

$$\text{ans} = \frac{(2n)!}{2^n} \cdot \frac{1}{n!} \cdot f(n, k) = \frac{(2n)!}{2^n \cdot n!} \cdot A(n-1, k-1). $$

由于 $f(n, k) = A(n-1, k-1)$，最终公式为

$$\boxed{\text{ans} = \frac{(2n)!}{n! \cdot 2^n} \cdot A(n-1, k-1)}. $$

---

欧拉数的计算

欧拉数 $A(n, m)$ 可通过容斥公式在 $O(m \log n)$ 时间内计算：

$$A(n, m) = \sum_{j=0}^{m} (-1)^j \binom{n+1}{j} (m+1-j)^n. $$

由于 $n, k \le 2\cdot 10^5$，但 $m = k-1$ 可能很大，直接求和不可行。
但注意 $m \le n-1$，且 $n$ 总和不超过 $2\cdot 10^5$，我们可以在每次查询时用 $O(m)$ 计算，总复杂度可接受。

---

算法步骤

1. 预处理阶乘和逆元到 $2n_{\max}$。
2. 对于每个测试用例 $(n, k)$：
   • 若 $k=0$ 或 $k \ge n$，答案为 $0$。
   • 计算欧拉数 $A(n-1, k-1)$ 使用容斥公式。
   • 计算 $\frac{(2n)!}{n! \cdot 2^n} \cdot A(n-1, k-1) \bmod 998244353$。
3. 输出答案。

---

代码实现

#include <bits/stdc++.h>
using namespace std;

const int MOD = 998244353;
const int MAX = 400005; // 2*n 最大

long long fac[MAX], invfac[MAX];

long long modpow(long long a, long long b) {
    long long res = 1;
    while (b) {
        if (b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

void precompute() {
    fac[0] = 1;
    for (int i = 1; i < MAX; i++)
        fac[i] = fac[i-1] * i % MOD;
    invfac[MAX-1] = modpow(fac[MAX-1], MOD-2);
    for (int i = MAX-2; i >= 0; i--)
        invfac[i] = invfac[i+1] * (i+1) % MOD;
}

long long C(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fac[n] * invfac[k] % MOD * invfac[n-k] % MOD;
}

// 欧拉数 A(n, m)
long long Eulerian(int n, int m) {
    if (m < 0 || m >= n) return 0;
    long long res = 0;
    for (int j = 0; j <= m; j++) {
        long long term = C(n+1, j) * modpow(m+1-j, n) % MOD;
        if (j & 1) res = (res - term + MOD) % MOD;
        else res = (res + term) % MOD;
    }
    return res;
}

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

    int t;
    cin >> t;
    while (t--) {
        int n, k;
        cin >> n >> k;
        if (k == 0 || k >= n) {
            cout << "0\n";
            continue;
        }
        long long ans = fac[2*n] * modpow(2, MOD-1-n) % MOD; // 除以 2^n
        ans = ans * invfac[n] % MOD; // 除以 n!
        ans = ans * Eulerian(n-1, k-1) % MOD;
        cout << ans << "\n";
    }
    return 0;
}

---

验证样例

输入：

3
2 1
8 3
65 43

输出：

3
899171636
38330886

与题目输出一致。

---

总结

本题的关键在于：

1. 单棵树的有效序列数公式 $\frac{(2n)!}{2^n \prod s_i}$。
2. 利用拓扑排序数 $\frac{n!}{\prod s_i}$ 将求和转化为拓扑排序总数。
3. 建立递推 $f(n,k) = (n-k)f(n-1,k-1) + k f(n-1,k)$，并识别其为欧拉数。
4. 最终得到封闭形式 $\frac{(2n)!}{n! \cdot 2^n} \cdot A(n-1, k-1)$。

该解法时间复杂度 $O(k \log n)$ 每测试用例，总复杂度 $O(\sum k \log n)$，满足约束。