Enter | Register

HOME TOP CATALOG CONTESTS GYM PROBLEMSET GROUPS RATING EDU API CALENDAR HELP

PROBLEMS SUBMIT STATUS STANDINGS CUSTOM TEST

Order Capital Round 2

I2. DBFS Order (Hard Version) (Codeforces Round 1104, Div. 1 +
Div. 2)
time limit per test: 2 seconds
Finished
memory limit per test: 1024 megabytes

This is the hard version of the problem. The difference between the versions is that in this version, the string s may → Virtual participation 
also contain character 1. You can hack only if you solved all versions of this problem.
Virtual contest is a way to take part in past
contest, as close as possible to participation
You are given a rooted tree with n vertices, rooted at vertex 1. For each vertex, its children are given in a fixed order.
on time. It is supported only ICPC mode for
virtual contests. If you've seen these
Each vertex except the root has a color, either 0 or 1. For a fixed coloring, define the following traversal. problems, a virtual contest is not for you -
solve these problems in the archive. If you
just want to solve some problem from a
p <- empty list contest, a virtual contest is not for you -
solve this problem in the archive. Never use
q <- deque containing only vertex 1 someone else's code, read the tutorials or
communicate with other person during a
virtual contest.
while q is not empty:
v <- the front element of q Start virtual contest
if v is not in p:
append v to p
if every child of v is already in p or in q:
→ Problem tags
pop the front element from q
dp trees
else: No tag edit access
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
→ Contest materials
else:
Announcement (en)
push u to the back of q
Tutorial (en)

After the process ends, the list p is called the traversal list of this coloring. It can be shown that p is always a permutation of
1, 2, … , n . In particular, if all colors are 0, then p is the DFS preorder of the tree; if all colors are 1, then p is the BFS order of

the tree, where children are visited in the given order.

You are given a string s of length n − 1, consisting of characters 0, 1, and ?. For each vertex i with 2 ≤ i ≤ n , the character
si−1 describes the possible color of vertex i :

if si−1 = 0 , then vertex i must have color 0;

if si−1 = 1 , then vertex i must have color 1;
if si−1 = ?, then vertex i may have color 0 or 1.

Find the number of distinct traversal lists that can be obtained over all valid colorings. Since the answer may be large, output it
modulo 109 + 7 .

Input
Each test contains multiple test cases. The first line contains the number of test cases t (1
4
≤ t ≤ 10 ). The description of the
test cases follows..

The first line of each test case contains an integer n (2 ≤ n ≤ 3000 ) — the number of vertices in the tree.

The second line contains a string s of length n − 1. In the hard version, s consists of characters 0, 1, and ?. The character si
describes the possible color of vertex i + 1.

The next n lines describe the ordered lists of children. The i -th of these lines first contains an integer li (0 ≤ li ≤ n − 1) —
the number of children of vertex i . Then follow li distinct integers ai,1 , ai,2 , … , ai,l (1 ≤ ai,j ≤ n ) — the children of vertex i
i

in their order.

It is guaranteed that the given ordered children lists describe a rooted tree with root 1.

6
It is guaranteed that the sum of n2 over all test cases does not exceed 9 ⋅ 10 .

Output
For each test case, output a single integer — the number of distinct traversal lists p that can be generated over all valid color
assignments, modulo 10
9
+ 7 .

Example
input Copy

10
4
1??
2 2 3
0
1 4
0
6
?????
5 2 3 4 5 6
0
0
0
0
0
12
?????1?010?
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
1 2
0
5
1?0?
1 2
1 3
1 4
1 5
0
5
1111
4 2 3 4 5
0
0
0
0
3
??
2 2 3
0
0
5
1???
2 2 3
2 4 5
0
0
0
7
?1?0??
2 2 3
2 4 5
2 6 7
0
0
0
0
8
1?0??1?
3 2 3 4
2 5 6
1 7
0
0
1 8
0
0

output Copy

3
27
88
1
1
1
2
6
8
14

Note
Let ci be the color of vertex i .

In the first test case, vertex 2 must have color 1, while vertices 3 and 4 are free.

If (c3 , c4 ) = (0, 0) , the traversal list is [1, 3, 4, 2] .

If (c3 , c4 ) = (0, 1) , the traversal list is [1, 3, 2, 4] .

If (c3 , c4 ) = (1, 0) or (c3 , c4 ) = (1, 1) , the traversal list is [1, 2, 3, 4] .

Thus there are 3 distinct traversal lists.

In the second test case, the tree is a star rooted at vertex 1, and all five leaves have free colors. A leaf with color 0 is visited
immediately when it is considered, while a leaf with color 1 is postponed until after all children of the root have been
5
considered. Among all 2 valid color assignments, there are 27 distinct traversal lists.

In the third test case, the free vertices are 2, 3, 4, 5, 6, 8, 12 . The fixed colors are c7 = 1 , c9 = 0 , c10 = 1 , and c11 = 0 .
Among all 27 valid color assignments, there are 88 distinct traversal lists.

Codeforces (c) Copyright 2010-2026 Mike Mirzayanov

The only programming contests Web 2.0 platform
Server time: Jun/20/2026 14:14:24UTC-6 (h1).
Desktop version, switch to mobile version.
Privacy Policy | Terms and Conditions

Supported by