#P18857. [Croatian CPC2025] Carsko Crnilo
[Croatian CPC2025] Carsko Crnilo
Carsko Crnilo
题目描述
给定一棵有 个顶点的无向树,顶点编号为 。你需要回答 次询问,每次给定 个互不相同的顶点 。
将树的每个顶点染成黑色或白色。如果染色满足以下全部条件,则称它为合法染色:
- 不存在两个相邻的黑色顶点。
- 顶点 全部为黑色。
- 对于每个黑色顶点,存在 ,使它位于 到 的最短路径上。允许 。
对每次询问,求合法染色的数量,答案对 取模。各次询问相互独立。
输入格式
第一行包含整数 。
接下来 行,每行包含整数 ,表示树的一条边。
接下来一行包含整数 。
接下来 行,每行先给出整数 ,然后给出 个互不相同的整数 。
输出格式
输出 行,每行一个整数,表示对应询问的答案模 的结果。
数据范围
- ,。
- 所有顶点编号均在 到 之间,输入的边构成一棵树。
- 所有询问的 之和不超过 。
样例 1
输入
9
1 2
2 3
1 4
4 5
5 6
1 7
7 8
7 9
10
1 4
2 1 8
2 1 6
2 1 4
3 1 3 8
3 1 8 9
3 3 6 7
4 3 6 8 9
4 3 5 8 9
5 1 3 6 8 9
输出
1
1
1
0
1
1
2
3
2
1