Imi 有一个无向树,有 $$$n$$$ 个顶点,边的编号从 $$$1$$$ 到 $$$n-1$$$。第 $$$i$$$ 条边连接顶点 $$$u_i$$$ 和 $$$v_i$$$。树上还有$$$k$$$蝴蝶。最初,第 $$$i$$$ 蝴蝶位于顶点 $$$a_i$$$ 上。 $$$a$$$ 的所有值都是成对不同的。
Koxia玩游戏如下:
- 对于 $$$i = 1, 2, \dots, n - 1$$$,Koxia 将第 $$$i$$$ 边的方向设置为 $$$u_i \rightarrow v_i$$$ 或 $$$v_i \rightarrow u_i$$$ 等概率。
- 对于$$$i = 1, 2, \dots, n - 1$$$,如果一只蝴蝶位于第$$$i$$$条边的初始顶点上,并且终端顶点上没有蝴蝶,则这只蝴蝶飞向终端顶点。请注意,操作按 $$$1, 2, \dots, n - 1$$$ 的顺序依次进行,而不是同时进行。
- Koxia 从 $$$k$$$ 蝴蝶中以相等的概率从所有可能的 $$$\frac{k(k-1)}{2}$$$ 方法中选择两只蝴蝶来选择两只蝴蝶,然后她将两个所选顶点之间的距离 $$$^\dagger$$$ 作为她的得分。
现在,Koxia 希望您找到她分数的期望值,以 $$$998\,244\,353^\ddagger$$$ 为模。
$$$^\dagger$$$ 树上两个顶点之间的距离是它们之间(唯一的)简单路径上的边数。
$$$^\ddagger$$$ 正式地,令 $$$M = 998\,244\,353$$$。可以证明,答案可以表示为不可约分数 $$$\frac{p}{q}$$$,其中 $$$p$$$ 和 $$$q$$$ 是整数,$$$q \not \equiv 0 \pmod{M}$$$。输出等于 $$$p \cdot q^{-1} \bmod M$$$ 的整数。换句话说,输出一个整数$$$x$$$,使得$$$0 \le x < M$$$ 且$$$x \cdot q \equiv p \pmod{M}$$$。
输入
第一行包含两个整数 $$$n$$$、$$$k$$$ ($$$2 \leq k \leq n \leq 3 \cdot {10}^5$$$) — 树的大小和蝴蝶的数量。
第二行包含 $$$k$$$ 整数 $$$a_1, a_2, \dots, a_k$$$ ($$$1 \leq a_i \leq n$$$) — 蝴蝶的初始位置。保证所有位置都是不同的。
以下 $$$n − 1$$$ 行中的第 $$$i$$$ 行包含两个整数 $$$u_i$$$、$$$v_i$$$ ($$$1 \leq u_i, v_i \leq n$$$, $$$u_i \neq v_i$$$) — 第 $$$i$$$ 条边连接的顶点。
保证给定的边形成一棵树。
输出
输出一个整数 — Koxia 分数的期望值,以 $$$998\,244\,353$$$ 为模。
示例
输入 #1
3 2 1 3 1 2 2 3
输出 #1
748683266
输入 #2
5 3 3 4 5 1 2 1 3 2 4 2 5
输出 #2
831870296
注意
在第一个测试用例中,树如下所示。包含蝴蝶的顶点被标记为粗体。
只有 $$$2$$$ 蝴蝶,因此蝴蝶的选择是固定的。让我们考虑以下 $$$4$$$ 案例:
- 边为 $$$1 \rightarrow 2$$$ 和 $$$2 \rightarrow 3$$$:顶点 $$$1$$$ 上的蝴蝶移动到顶点 $$$2$$$,但顶点 $$$3$$$ 上的蝴蝶不移动。顶点 $$$2$$$ 和 $$$3$$$ 之间的距离为 $$$1$$$。
- 边为 $$$1 \rightarrow 2$$$ 和 $$$3 \rightarrow 2$$$:顶点 $$$1$$$ 上的蝴蝶移动到顶点 $$$2$$$,但顶点 $$$3$$$ 上的蝴蝶无法移动到顶点 $$$2$$$,因为它已被占用。顶点 $$$2$$$ 和 $$$3$$$ 之间的距离为 $$$1$$$。
- 边为 $$$2 \rightarrow 1$$$ 和 $$$2 \rightarrow 3$$$:顶点 $$$1$$$ 和顶点 $$$3$$$ 上的蝴蝶都不会移动。顶点 $$$1$$$ 和 $$$3$$$ 之间的距离是 $$$2$$$。
- 边为 $$$2 \rightarrow 1$$$ 和 $$$3 \rightarrow 2$$$:顶点 $$$1$$$ 上的蝴蝶不移动,但顶点 $$$3$$$ 上的蝴蝶移动到顶点 $$$2$$$。顶点 $$$1$$$ 和 $$$2$$$ 之间的距离为 $$$1$$$。
因此,Koxia 得分的期望值为 $$$\frac {1+1+2+1} {4} = \frac {5} {4}$$$,模 $$$998\,244\,353$$$ 后为 $$$748\,683\,266$$$。
在第二个测试用例中,树如下所示。包含蝴蝶的顶点被标记为粗体。 Koxia 分数的期望值为 $$$\frac {11} {6}$$$,模 $$$998\,244\,353$$$ 后为 $$$831\,870\,296$$$。