Koxia 与树

• 时间限制：3 秒
• 内存限制：512 MiB

题目描述

给定一棵有 $n$ 个顶点的无向树，边按照输入顺序编号为 $1,2,\ldots,n-1$。树上有 $k$ 只蝴蝶，它们最初分别位于两两不同的顶点 $a_1,a_2,\ldots,a_k$。

Koxia 进行如下游戏：

1. 对每条边独立地等概率选择两个方向之一。
2. 按照边编号从 $1$ 到 $n-1$ 依次处理。若当前边的起点有蝴蝶且终点没有蝴蝶，这只蝴蝶就沿边飞到终点。所有操作是依次进行的，并非同时进行。
3. 在所有 $\binom{k}{2}$ 对蝴蝶中等概率选择一对，以它们最终所在顶点之间的树上距离作为得分。

求得分的数学期望，对 $998244353$ 取模。

若期望为既约分数 $p/q$，输出 $p\cdot q^{-1}\bmod 998244353$。

输入格式

第一行包含两个整数 $n,k$。

第二行包含 $k$ 个两两不同的整数 $a_1,a_2,\ldots,a_k$，表示蝴蝶的初始位置。

随后 $n-1$ 行，第 $i$ 行包含两个整数 $u_i,v_i$，表示编号为 $i$ 的边连接这两个顶点。

输出格式

输出一个整数，表示得分的数学期望对 $998244353$ 取模后的结果。

样例输入 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\le k\le n\le 3\times 10^5$；
• $1\le a_i,u_i,v_i\le n$；
• $a_i$ 两两不同；
• 输入的 $n-1$ 条边构成一棵树。

说明

第一组样例中四种边方向下的距离之和为 $5$，所以期望为 $5/4$。

题目来源：Codeforces 1770E。