#P10894. 虚树

虚树

题目背景

首先,做这道题不需要用到任何虚树有关知识。

——尽管这是主题库里第一个名字含“虚树”的题(

题目描述

jq 姐姐有一棵以结点 11 为根的树。定义一棵树的点集 SS 的非空子集 ss 是好的,当且仅当它满足 i,js,LCA(i,j)s\forall i,j \in s, \text{LCA}(i,j) \in s什么是 LCA\text{LCA}

为了让树的形态更加可爱,jq 姐姐打算修剪掉某个以节点 ii 为根的子树(也就是在原树里将节点 ii 及其子树内节点及其相连的边均删除)。

她有若干个修剪方案但从未实施,你需要求出每种方案实施后这棵树的好的非空子集数量。由于答案可能会很大,请输出其对 998244353998244353 取模的结果。

输入格式

第一行读入一个整数 nn (n5×105n \leq 5 \times 10^5),表示树的节点数。

22nn 行,每行读入两个整数 ui,viu_i,v_i,表示一条从 uiu_i 连向 viv_i 的边。

n+1n+1 行读入一个整数 mm (m5×105m \leq 5 \times 10^5),表示修剪方案数。

接下来一行每行读入 mm 个整数 qiq_i,表示将以 qiq_i 为根的子树修剪掉。

输出格式

mm 行,第 ii 行一个整数 kk 表示删除以 qiq_i 为根的子树后原树的好的非空子集数量。

5
1 2
2 3
2 4
1 5
2
2 5
3
13
10
1 2
2 3
2 4
1 5
5 6
5 7
7 8
7 10
1 9
3
5 2 8
21
66
201

提示

样例 1 解释:删去以 22 为根的子树后,原树点集的 33 个非空子集均满足性质,删去以 55 为根的子树后,原树点集的 1515 个非空子集中有 {3,4}\{3,4\}{1,3,4}\{1,3,4\} 不满足性质。

对于前 10%10\% 的数据,n,m20n,m \leq 20

对于前 30%30\% 的数据,n,m3000n,m \leq 3000

对于 100%100\% 的数据,1n,m5×1051 \leq n,m \leq 5 \times 10^5q[1,n]q \in [1,n]