题目描述

You are given a rooted tree with $n$ vertices. The root of the tree is vertex $1$.

Each vertex $i$ has a value $a_i$, which is either $0$ or $1$.

For each size $k$ ($1 \le k \le n$), determine which xor values can be obtained by choosing a set of vertices $S$ that satisfies the following conditions:

• $|S| = k$;
• if vertex $v$ belongs to the set $S$, then all vertices in the subtree of vertex $v$ also belong to $S$.

The value of a set $S$ is defined as the xor of the values of all vertices in this set: $\bigoplus_{v \in S} a_v.$

The subtree of vertex $v$ is the set of all vertices $u$ such that vertex $v$ lies on the simple path from the root $1$ to vertex $u$.

The xor operation for bits is defined as follows: $0 \oplus 0 = 0, 0 \oplus 1 = 1, 1 \oplus 0 = 1, 1 \oplus 1 = 0.$

The child of vertex $v$ is a vertex whose parent is $v$.

输入格式

The first line contains one integer $t$ ($1 \le t \le 1000$) --- the number of test cases.

Each test case consists of three lines.

The first line of each test case contains one integer $n$ ($2 \le n \le 4 \cdot 10^5$) --- the number of vertices in the tree.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($a_i \in \{0, 1\}$) --- the values of the vertices.

The third line contains $n-1$ integers $p_2, p_3, \ldots, p_n$ ($1 \le p_i < i$), where $p_i$ is the parent of vertex $i$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $4 \cdot 10^5$.

输出格式

For each test case, output one line with $n$ integers $ans_1, ans_2, \ldots, ans_n$.

For each $k$:

• $ans_k = 0$, if among all valid sets of size $k$ only xor $0$ can be obtained;
• $ans_k = 1$, if among all valid sets of size $k$ only xor $1$ can be obtained;
• $ans_k = 2$, if among all valid sets of size $k$ both xor $0$ and xor $1$ can be obtained.

2
5
1 0 1 1 0
1 2 1 4
9
0 0 0 1 1 1 1 1 1
1 2 3 2 4 4 6 8

2 1 2 0 1 
1 0 1 0 1 2 0 0 0 

提示

This is what the trees in the first and second test cases look like, respectively.

:::align{center} :::

Consider the first test case.

For $k = 1$, both xor values can be obtained. For example, the set $S = \{5\}$ is valid and has xor $0$. And the set $S = \{3\}$ is also valid and has xor $1$. Therefore, $ans_1 = 2$.

For $k = 3$, both xor values can also be obtained. For example, the set $S = \{2, 3, 5\}$ is valid because together with vertex $2$ all vertices in its subtree are chosen. Its xor is $a_2 \oplus a_3 \oplus a_5 = 0 \oplus 1 \oplus 0 = 1$. And the set $S = \{3, 4, 5\}$ is also valid because together with vertex $4$ all vertices in its subtree are chosen. Its xor is $a_3 \oplus a_4 \oplus a_5 = 1 \oplus 1 \oplus 0 = 0$. Therefore, $ans_3 = 2$.

Thus, the answer for the first test case is $2\ 1\ 2\ 0\ 1$.

Consider the second test case.

In this test case, both xor values can be obtained only for $k = 6$.

For example, the set $S = \{3, 4, 6, 7, 8, 9\}$ is valid. Its xor is $a_3 \oplus a_4 \oplus a_6 \oplus a_7 \oplus a_8 \oplus a_9 = 0 \oplus 1 \oplus 1 \oplus 1 \oplus 1 \oplus 1 = 1$.

And the set $S = \{4, 5, 6, 7, 8, 9\}$ is also valid. Its xor is $a_4 \oplus a_5 \oplus a_6 \oplus a_7 \oplus a_8 \oplus a_9 = 1 \oplus 1 \oplus 1 \oplus 1 \oplus 1 \oplus 1 = 0$. Therefore, $ans_6 = 2$.

Thus, the answer for the second test case is $1\ 0\ 1\ 0\ 1\ 2\ 0\ 0\ 0$.

Scoring

A leaf is a vertex that has no children.

A bamboo is a tree in which every vertex has at most one child.

• ($2$ points): $\sum n \le 20$;
• ($3$ points): $p_i=1$;
• ($5$ points): $\sum n^3 \le 10^8$;
• ($8$ points): $\sum n^2 \le 10^8$;
• ($12$ points): the total number of leaves over all test cases does not exceed $100$;
• ($8$ points): after removing vertex $1$, each component is a bamboo, and there are at most two such components;
• ($9$ points): after removing vertex $1$, each component is a bamboo;
• ($9$ points): all trees are full binary trees, that is, $n = 2^q - 1$ for some integer $q$, and for every vertex $i > 1$ we have $p_i = \left\lfloor \frac{i}{2} \right\rfloor$;
• ($22$ points): $n \le 2 \cdot 10^5$ for each test case;
• ($22$ points): no additional constraints.