CF1770E.Koxia and Tree

Imi has an undirected tree with $n$ vertices where edges are numbered from $1$ to $n-1$. The $i$-th edge connects vertices $u_i$ and $v_i$. There are also $k$ butterflies on the tree. Initially, the $i$-th butterfly is on vertex $a_i$. All values of $a$ are pairwise distinct.

Koxia plays a game as follows:

• For $i = 1, 2, \dots, n - 1$, Koxia set the direction of the $i$-th edge as $u_i \rightarrow v_i$ or $v_i \rightarrow u_i$ with equal probability.
• For $i = 1, 2, \dots, n - 1$, if a butterfly is on the initial vertex of $i$-th edge and there is no butterfly on the terminal vertex, then this butterfly flies to the terminal vertex. Note that operations are sequentially in order of $1, 2, \dots, n - 1$ instead of simultaneously.
• Koxia chooses two butterflies from the $k$ butterflies with equal probability from all possible $\frac{k(k-1)}{2}$ ways to select two butterflies, then she takes the distance$^\dagger$ between the two chosen vertices as her score.

Now, Koxia wants you to find the expected value of her score, modulo $998\,244\,353^\ddagger$.

$^\dagger$ The distance between two vertices on a tree is the number of edges on the (unique) simple path between them.

$^\ddagger$ Formally, let $M = 998\,244\,353$. It can be shown that the answer can be expressed as an irreducible fraction $\frac{p}{q}$, where $p$ and $q$ are integers and $q \not \equiv 0 \pmod{M}$. Output the integer equal to $p \cdot q^{-1} \bmod M$. In other words, output such an integer $x$ that $0 \le x \lt M$ and $x \cdot q \equiv p \pmod{M}$.

伊米有一棵包含 $n$ 个顶点的无向树，其边编号为 $1$ 到 $n-1$。第 $i$ 条边连接顶点 $u_i$ 和 $v_i$。树上还有 $k$ 只蝴蝶。初始时，第 $i$ 只蝴蝶位于顶点 $a_i$。所有 $a_i$ 的值两两不同。

小霞进行如下游戏：

• 对于 $i = 1, 2, \dots, n - 1$，小霞以相等概率将第 $i$ 条边定向为 $u_i \rightarrow v_i$ 或 $v_i \rightarrow u_i$；
• 对于 $i = 1, 2, \dots, n - 1$，若某只蝴蝶位于第 $i$ 条边的起点，且终点处没有蝴蝶，则该蝴蝶飞向终点。注意：这些操作按顺序依次执行（即先处理边 $1$，再边 $2$，……，最后边 $n-1$），而非同时进行；
• 小霞从 $k$ 只蝴蝶中等概率地随机选出两只（共 $\frac{k(k-1)}{2}$ 种选法），并将这两只蝴蝶所在顶点之间的距离$^\dagger$ 作为她的得分。

现在，小霞希望你计算她得分的期望值，并对 $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}$。

The first line contains two integers $n$, $k$ ($2 \leq k \leq n \leq 3 \cdot {10}^5$) — the size of the tree and the number of butterflies.

The second line contains $k$ integers $a_1, a_2, \dots, a_k$ ($1 \leq a_i \leq n$) — the initial position of butterflies. It's guaranteed that all positions are distinct.

The $i$-th line in following $n − 1$ lines contains two integers $u_i$, $v_i$ ($1 \leq u_i, v_i \leq n$, $u_i \neq v_i$) — the vertices the $i$-th edge connects.

It is guaranteed that the given edges form a tree.

第一行包含两个整数 $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$ 条边所连接的两个顶点。

保证给定的边构成一棵树。

Output a single integer — the expected value of Koxia's score, modulo $998\,244\,353$.

输出一个整数——Koxia 得分的期望值对 $998\,244\,353$ 取模的结果。

In the first test case, the tree is shown below. Vertices containing butterflies are noted as bold.

There are only $2$ butterflies so the choice of butterflies is fixed. Let's consider the following $4$ cases:

• Edges are $1 \rightarrow 2$ and $2 \rightarrow 3$: butterfly on vertex $1$ moves to vertex $2$, but butterfly on vertex $3$ doesn't move. The distance between vertices $2$ and $3$ is $1$.
• Edges are $1 \rightarrow 2$ and $3 \rightarrow 2$: butterfly on vertex $1$ moves to vertex $2$, but butterfly on vertex $3$ can't move to vertex $2$ because it's occupied. The distance between vertices $2$ and $3$ is $1$.
• Edges are $2 \rightarrow 1$ and $2 \rightarrow 3$: butterflies on both vertex $1$ and vertex $3$ don't move. The distance between vertices $1$ and $3$ is $2$.
• Edges are $2 \rightarrow 1$ and $3 \rightarrow 2$: butterfly on vertex $1$ doesn't move, but butterfly on vertex $3$ move to vertex $2$. The distance between vertices $1$ and $2$ is $1$.

Therefore, the expected value of Koxia's score is $\frac {1+1+2+1} {4} = \frac {5} {4}$, which is $748\,683\,266$ after modulo $998\,244\,353$.

In the second test case, the tree is shown below. Vertices containing butterflies are noted as bold. The expected value of Koxia's score is $\frac {11} {6}$, which is $831\,870\,296$ after modulo $998\,244\,353$.

在第一个测试用例中，树的结构如下图所示。包含蝴蝶的顶点以粗体标出。

共有且仅有 $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$。