这是问题的困难版本。版本之间的区别在于,在这个版本中,字符串 $$$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, 1,和 ?。字符$$$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$$$ 为模。
示例
输入复制
1041??2 2 301 406?????5 2 3 4 5 60000012?????1?010?1 112 8 33 9 12 601 401 1001 502 2 70211 2051?0?1 21 31 41 50511114 2 3 4 500003??2 2 30051???2 2 32 4 50007?1?0??2 2 32 4 52 6 7000081?0??1?3 2 3 42 5 61 7001 800
输出复制
3278811126814
注意
设 $$$c_i$$$ 为顶点 $$$i$$$ 的颜色。
在第一个测试用例中,顶点 $$$2$$$ 必须具有颜色 $$$1$$$,而顶点 $$$3$$$ 和 $$$4$$$ 是自由的。
如果$$$(c_3,c_4)=(0,0)$$$,则遍历列表为$$$[1,3,4,2]$$$。
如果$$$(c_3,c_4)=(0,1)$$$,则遍历列表为$$$[1,3,2,4]$$$。
如果$$$(c_3,c_4)=(1,0)$$$或$$$(c_3,c_4)=(1,1)$$$,则遍历列表为$$$[1,2,3,4]$$$。
因此有 $$$3$$$ 不同的遍历列表。
在第二个测试用例中,树是一颗以顶点 $$$1$$$ 为根的星形树,所有五个叶子都有自由颜色。颜色为 $$$0$$$ 的叶子在考虑时会立即被访问,而颜色为 $$$1$$$ 的叶子会被推迟,直到根的所有子节点都被考虑之后。在所有 $$$2^5$$$ 有效颜色分配中,有 $$$27$$$ 不同的遍历列表。
在第三个测试用例中,自由顶点是 $$$2,3,4,5,6,8,12$$$。固定颜色为 $$$c_7=1$$$、$$$c_9=0$$$、$$$c_{10}=1$$$ 和 $$$c_{11}=0$$$。在所有 $$$2^7$$$ 有效颜色分配中,有 $$$88$$$ 不同的遍历列表。