1009. 引力场

题目描述

在遥远的乱星海，岛屿星罗棋布，无数的修士在此间来往交易。只是此地海域辽阔，兽潮不定，若仅靠御器飞遁，既耗费法力，又容易遭遇妖兽与杀人夺宝之辈。因此，各大商会共同修建了一套特殊的物流运输系统。物流运输系统由 n 个节点与 n − 1 条双向道路构成，每条双向道路连接两个不同的节点，任意两个不同的节点都可以通过若干条双向道路到达。换言之，这些节点的连接形成了一棵树。有一天，河灵和胖胖龙达成了一笔交易。河灵需要将包裹从节点 s 运输到节点 t（允许 s, t 相同）。包裹的运输依赖于这套物流运输系统，每个节点都有一个特殊的引力装置。当节点 x 的引力装置被激活时，将会在节点 x 上开启短暂的局部引力场：

• 若此时包裹处于某个和节点 x 直接相连的节点上，那么包裹将会被移动到节点 x 上。

• 否则，包裹的位置保持不变。

每个节点的引力装置被激活时，其效果将立即生效，随后自动关闭，不会对后续的激活产生影响。然而，运输系统由商会管理。商会将会选择一个关于 n 的排列

p1, …, pn，并依次激活节点 p1, …, pn 上的引力装置。每个节点的引

力装置都会被恰好激活一次。河灵想知道，在 n! 种不同的节点激活顺序中，有多少种节点激活顺序

p1, …, pn 可以使得初始在节点 s 的包裹，在所有节点的引力装置都激活完毕之后恰好停留在节点 t。答案对 998244353 取模。

输入格式

每个测试点中包含多组测试数据。输入的第一行包含一个正整数 T (

1 ≤ T ≤ 5 × 105 )，表示数据组数。对于每组测试数据：第一行三个正整数 n, s, t (1 ≤ n ≤ 105, 1 ≤ s, t ≤ n)，表示节点个数，起点与终点。接下来 n − 1 行，每行两个正整数 x, y (1 ≤ x, y ≤ n)，表示存在一条双向道路连接节点 x, y。保证所有测试数据中 n 之和不超过 5 × 105。

输出格式

对于每组测试数据：输出一行一个整数，表示答案对 998244353 取模后的值。

样例输入

4
5 2 5
1 2
1 3
1 4
1 5
11 1 11
1 2
10 1
3 10
11 10
4 11
6 11
5 11
7 10
9 1
1 8
9 3 1
1 2
2 3
3 4
3 5
4 9
4 8
5 6
5 7
16 1 1
1 2
2 3
1 4
4 5
4 6
1 7
7 8
7 9
7 10
1 11
11 12
11 13
11 15
11 16
13 14

样例输出

24
868392
65952
479108505

来源：官方题面 PDF（2026"钉耙编程"暑期联赛 第2场）