#P10894. 虚树
虚树
题目背景
首先,做这道题不需要用到任何虚树有关知识。
——尽管这是主题库里第一个名字含“虚树”的题(
题目描述
jq 姐姐有一棵以结点 为根的树。定义一棵树的点集 的非空子集 是好的,当且仅当它满足 。什么是 ?
为了让树的形态更加可爱,jq 姐姐打算修剪掉某个以节点 为根的子树(也就是在原树里将节点 及其子树内节点及其相连的边均删除)。
她有若干个修剪方案但从未实施,你需要求出每种方案实施后这棵树的好的非空子集数量。由于答案可能会很大,请输出其对 取模的结果。
输入格式
第一行读入一个整数 (),表示树的节点数。
第 到 行,每行读入两个整数 ,表示一条从 连向 的边。
第 行读入一个整数 (),表示修剪方案数。
接下来一行每行读入 个整数 ,表示将以 为根的子树修剪掉。
输出格式
共 行,第 行一个整数 表示删除以 为根的子树后原树的好的非空子集数量。
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 解释:删去以 为根的子树后,原树点集的 个非空子集均满足性质,删去以 为根的子树后,原树点集的 个非空子集中有 、 不满足性质。
对于前 的数据,。
对于前 的数据,。
对于 的数据,,。