P16459 [UOI 2026] Tree Subsets

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.

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.