#216498. [UOI 2026] Tree Subsets

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

Each vertex has a value , which is either or .

For each size (), determine which xor values can be obtained by choosing a set of vertices that satisfies the following conditions:

• ;
• if vertex belongs to the set , then all vertices in the subtree of vertex also belong to .

The value of a set is defined as the xor of the values of all vertices in this set:

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

The xor operation for bits is defined as follows:

The child of vertex is a vertex whose parent is .

The first line contains one integer () --- the number of test cases.

Each test case consists of three lines.

The first line of each test case contains one integer () --- the number of vertices in the tree.

The second line contains integers () --- the values of the vertices.

The third line contains integers (), where is the parent of vertex .

It is guaranteed that the sum of over all test cases does not exceed .

For each test case, output one line with integers .

For each :

• , if among all valid sets of size only xor can be obtained;
• , if among all valid sets of size only xor can be obtained;
• , if among all valid sets of size both xor and xor can be obtained.

样例输入 1

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

样例输出 1

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 , both xor values can be obtained. For example, the set is valid and has xor . And the set is also valid and has xor . Therefore, .

For , both xor values can also be obtained. For example, the set is valid because together with vertex all vertices in its subtree are chosen. Its xor is . And the set is also valid because together with vertex all vertices in its subtree are chosen. Its xor is . Therefore, .

Thus, the answer for the first test case is .

Consider the second test case.

In this test case, both xor values can be obtained only for .

For example, the set is valid. Its xor is .

And the set is also valid. Its xor is . Therefore, .

Thus, the answer for the second test case is .

Scoring

A leaf is a vertex that has no children.

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

• ( points): ;
• ( points): ;
• ( points): ;
• ( points): ;
• ( points): the total number of leaves over all test cases does not exceed ;
• ( points): after removing vertex , each component is a bamboo, and there are at most two such components;
• ( points): after removing vertex , each component is a bamboo;
• ( points): all trees are full binary trees, that is, for some integer , and for every vertex we have ;
• ( points): for each test case;
• ( points): no additional constraints.