← 返回题目列表

Codeforces · 2237/I1

I1. DBFS 顺序(简易版)

中文机器翻译题面 查看原题

这是问题的简单版本。版本之间的区别在于,在此版本中,字符串 $$$s$$$ 不包含任何字符 1。只有解决了该问题的所有版本,您才能破解。

给你一棵有 $$$n$$$ 个顶点的有根树,根在顶点 $$$1$$$ 处。对于每个顶点,其子顶点均按固定顺序给出。

除根之外的每个顶点都有一种颜色,可以是 $$$0$$$ 或 $$$1$$$。对于固定着色,定义以下遍历。

p <- empty list
q <- deque containing only vertex 1

while q is not empty:
v <- the front element of q
if v is not in p:
append v to p
if every child of v is already in p or in q:
pop the front element from q
else:
u <- the first child of v that is neither in p nor in q
if color[u] = 0:
push u to the front of q
else:
push u to the back of q

流程结束后,列表$$$p$$$称为该着色的遍历列表。可以证明$$$p$$$始终是$$$1,2,\ldots,n$$$的排列。特别是,如果所有颜色都是$$$0$$$,那么$$$p$$$就是树的DFS前序;如果所有颜色都是 $$$1$$$,则 $$$p$$$ 是树的 BFS 顺序,其中子级按给定顺序被访问。

给定一个字符串 $$$s$$$,长度为 $$$n-1$$$,由字符组成 0, 1,和 ?。对于 $$$2\le i\le n$$$ 的每个顶点 $$$i$$$,字符 $$$s_{i-1}$$$ 描述了顶点 $$$i$$$ 可能的颜色:

  • 如果 $$$s_{i-1}=\texttt{0}$$$,则顶点 $$$i$$$ 必须具有颜色 $$$0$$$;
  • 如果 $$$s_{i-1}=\texttt{1}$$$,则顶点 $$$i$$$ 必须具有颜色 $$$1$$$;
  • 如果 $$$s_{i-1}=\texttt{?}$$$,则顶点 $$$i$$$ 可能具有颜色 $$$0$$$ 或 $$$1$$$。

找出在所有有效着色上可以获得的不同遍历列表的数量。由于答案可能很大,因此输出它对 $$$10^9+7$$$ 取模。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下:

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 3000$$$) — 树中的顶点数。

第二行包含长度为 $$$n-1$$$ 的字符串 $$$s$$$。在简单版本中,$$$s$$$ 仅由字符组成 0 和 ?。字符$$$s_i$$$描述了顶点$$$i+1$$$可能的颜色。

接下来的 $$$n$$$ 行描述子项的有序列表。这些行中的第 $$$i$$$ 首先包含一个整数 $$$l_i$$$ ($$$0 \le l_i \le n-1$$$) — 顶点 $$$i$$$ 的子节点数。然后跟随 $$$l_i$$$ 不同的整数 $$$a_{i,1},a_{i,2},\ldots,a_{i,l_i}$$$ ($$$1 \le a_{i,j} \le n$$$) — 顶点 $$$i$$$ 的子节点(按顺序排列)。

保证给定的有序子列表描述了一个根为 $$$1$$$ 的有根树。

保证所有测试用例的 $$$n^2$$$ 总和不超过 $$$9 \cdot 10^6$$$。

输出

对于每个测试用例,输出一个整数 - 可以在所有有效颜色分配上生成的不同遍历列表 $$$p$$$ 的数量,以 $$$10^9 + 7$$$ 为模。

示例

输入
复制

10
4
?0?
2 2 3
0
1 4
0
6
?????
5 2 3 4 5 6
0
0
0
0
0
12
?????0?000?
1 11
2 8 3
3 9 12 6
0
1 4
0
1 10
0
1 5
0
2 2 7
0
2
?
1 2
0
5
????
1 2
1 3
1 4
1 5
0
5
0000
4 2 3 4 5
0
0
0
0
3
??
2 2 3
0
0
5
????
2 2 3
2 4 5
0
0
0
7
??????
2 2 3
2 4 5
2 6 7
0
0
0
0
8
??0?0??
3 2 3 4
2 5 6
1 7
0
0
1 8
0
0

输出
复制

3
27
75
1
1
1
2
7
30
26

注意

设 $$$c_i$$$ 为顶点 $$$i$$$ 的颜色。

在第一个测试用例中,顶点 $$$3$$$ 必须具有颜色 $$$0$$$,而顶点 $$$2$$$ 和 $$$4$$$ 是自由的。

如果$$$(c_2,c_4)=(0,0)$$$或$$$(c_2,c_4)=(0,1)$$$,则遍历列表为$$$[1,2,3,4]$$$。

如果$$$(c_2,c_4)=(1,0)$$$,则遍历列表为$$$[1,3,4,2]$$$。

如果$$$(c_2,c_4)=(1,1)$$$,则遍历列表为$$$[1,3,2,4]$$$。

因此有 $$$3$$$ 不同的遍历列表。

在第二个测试用例中,树是一颗以顶点 $$$1$$$ 为根的星形树,所有五个叶子都有自由颜色。颜色为 $$$0$$$ 的叶子在考虑时会立即被访问,而颜色为 $$$1$$$ 的叶子会被推迟,直到根的所有子节点都被考虑之后。在所有 $$$2^5$$$ 有效颜色分配中,有 $$$27$$$ 不同的遍历列表。

在第三个测试用例中,自由顶点是 $$$2,3,4,5,6,8,12$$$。固定颜色为 $$$c_7=0$$$、$$$c_9=0$$$、$$$c_{10}=0$$$ 和 $$$c_{11}=0$$$。在所有 $$$2^7$$$ 有效颜色分配中,有 $$$75$$$ 不同的遍历列表。