#P18857. [Croatian CPC2025] Carsko Crnilo

[Croatian CPC2025] Carsko Crnilo

Carsko Crnilo

题目描述

给定一棵有 NN 个顶点的无向树,顶点编号为 1,2,…,N1,2,\ldots,N。你需要回答 QQ 次询问,每次给定 KK 个互不相同的顶点 A1,…,AKA_1,\ldots,A_K。

将树的每个顶点染成黑色或白色。如果染色满足以下全部条件,则称它为合法染色:

  • 不存在两个相邻的黑色顶点。
  • 顶点 A1,…,AKA_1,\ldots,A_K 全部为黑色。
  • 对于每个黑色顶点,存在 1≤i≤j≤K1\le i\le j\le K,使它位于 AiA_i 到 AjA_j 的最短路径上。允许 i=ji=j。

对每次询问,求合法染色的数量,答案对 109+710^9+7 取模。各次询问相互独立。

输入格式

第一行包含整数 NN。

接下来 N−1N-1 行,每行包含整数 ui,viu_i,v_i,表示树的一条边。

接下来一行包含整数 QQ。

接下来 QQ 行,每行先给出整数 KK,然后给出 KK 个互不相同的整数 A1,…,AKA_1,\ldots,A_K。

输出格式

输出 QQ 行,每行一个整数,表示对应询问的答案模 109+710^9+7 的结果。

数据范围

  • 1≤N,Q≤2×1051\le N,Q\le2\times10^5,1≤K≤N1\le K\le N。
  • 所有顶点编号均在 11 到 NN 之间,输入的边构成一棵树。
  • 所有询问的 KK 之和不超过 2×1052\times10^5。

样例 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