CF2237I2 DBFS Order (Hard Version)

这是该问题的Hard版本。两个版本的区别在于，本版本中字符串 $s$ 可能还包含字符 1。只有在你解决了所有版本的本题后才能进行 Hack。 给你一棵有 $n$ 个结点的有根树，根为结点 1。对于每个结点，其子结点给定了一个固定的顺序。 除根结点外，每个结点都有颜色，颜色为 $0$ 或 $1$。对于一种固定染色，定义如下遍历方式。 ``` p ← 空列表 q ← 只包含结点 1 的双端队列 while q 非空： v ← q 的队首元素 if v 不在 p 中： 将 v 加入 p if v 的所有子结点都已在 p 或 q 中： 从 q 队首移除元素 else: u ← v 首个既不在 p 也不在 q 中的子结点 if color[u] = 0: 把 u 推入 q 的队首 else: 把 u 推入 q 的队尾 ``` 这个过程结束后，列表 $p$ 被称为该染色的遍历序列。可以证明 $p$ 始终是 $1,2,\ldots,n$ 的一个排列。特别地，若所有颜色均为 $0$，则 $p$ 就是树的 DFS 先序遍历；若所有颜色均为 $1$，则 $p$ 是树的 BFS 遍历（按给定的儿子顺序遍历）。 给定一个长度为 $n-1$ 的字符串 $s$，由字符 0、1 和 ? 组成。对于每个 $2\le i\le n$，字符 $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$。在 Hard 版本中，$s$ 由字符 0, 1, ? 组成，字符 $s_i$ 描述结点 $i+1$ 的可能颜色。 接下来 $n$ 行描述有序的子结点列表。第 $i$ 行首先包含一个整数 $l_i$（$0 \le l_i \le n-1$），接下来有 $l_i$ 个两两不同的整数 $a_{i,1},a_{i,2},\ldots,a_{i,l_i}$（$1 \le a_{i,j} \le n$），表示结点 $i$ 的儿子，以给定顺序排列。 保证给定的有序子结点列表是一棵以 $1$ 为根的树。 保证所有测试用例中 $\sum n^2 \le 9 \times 10^6$。

对于每组测试用例，输出一个整数，表示所有有效染色下能产生的不同遍历序列 $p$ 的种数，对 $10^9 + 7$ 取模。

令 $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$ 为根的星形，所有 5 个叶子的颜色都可任意选择。当一个叶结点颜色为 $0$ 时会立即访问，否则会等到根所有子结点都被考虑后才访问。在所有 $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$ 种遍历序列。 由 ChatGPT 5 翻译