CF2122G Tree Parking

给定一棵以 $1$ 为根的 $n$ 个结点的树。对于每个 $1 \leq i \leq n$，一辆汽车会在时间 $l_i$ 进入根节点，然后沿着唯一的简单路径瞬间到达结点 $i$ 并停在那里。它会在时间 $r_i$ 沿着相同的路径反方向离开。 当一辆车停在某个结点时，会阻塞其他车辆通过该结点。只有当所有车辆都能在期望的时间进入和离开树时，这棵树才被称为“有效”。 请统计满足以下条件的序列对 $(l, r)$ 的数量： - 对于每个 $i$，有 $l_i < r_i$。 - $l$ 和 $r$ 拼接后是 $1 \ldots 2n$ 的一个排列。 - 该树是有效的。 计算所有有 $n$ 个结点且有 $k$ 个叶子的有标号树 $^{\ast}$ 的答案之和。根节点不算作叶子。由于答案可能很大，请对 $998\,244\,353$ 取模。 $^{\ast}$ 两棵有标号树只有当它们的边集不同才被认为是不同的。

每个测试点包含多组测试数据。第一行包含测试数据组数 $t$（$1 \le t \le 10^4$）。 接下来每组测试数据一行，包含两个整数 $n$ 和 $k$（$1 \leq k < n \leq 2 \cdot 10^5$），分别表示结点数和叶子数。 保证所有测试数据中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每组测试数据，输出一个整数，表示答案对 $998\,244\,353$ 取模后的结果。

在第一个样例中，只有一棵满足条件的树。合法的序列对有： $(l, r) = ([1, 3], [2, 4]),\ ([3, 1], [4, 2]),\ ([2, 1], [3, 4])$。 由 ChatGPT 4.1 翻译