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 → Virtual participation
this version, the string s may 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
on time. It is supported only ICPC mode for
You are given a rooted tree with n vertices, rooted at vertex 1. For each vertex, its children virtual contests. If you've seen these
problems, a virtual contest is not for you -
are given in a fixed order.
solve these problems in the archive. If you
just want to solve some problem from a
Each vertex except the root has a color, either 0 or 1. For a fixed coloring, define the following contest, a virtual contest is not for you -
solve this problem in the archive. Never use
traversal. someone else's code, read the tutorials or
communicate with other person during a
virtual contest.
p <- empty list
q <- deque containing only vertex 1 Start virtual contest
while q is not empty:
v <- the front element of q → Problem tags
if v is not in p:
dp trees
append v to p
No tag edit access
if every child of v is already in p or in q:
pop the front element from q
else: → Contest materials
u <- the first child of v that is neither in p nor in q
Announcement (en)
if color[u] = 0:
push u to the front of q Tutorial (en)
else:
push u to the back of q
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 10
9
+ 7 .
Input
Each test contains multiple test cases. The first line contains the number of test cases t (
4
1 ≤ 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 in their order.
i
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 considered. Among all 25 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/23/2026 12:50:00UTC+5.5 (i1).
Desktop version, switch to mobile version.
Privacy Policy | Terms and Conditions
Supported by