当前没有测试数据。

2s 512M

题目描述

给定一棵有 $n$ 个顶点的有根树，树根为顶点 $1$。

每个顶点 $i$ 有一个值 $a_i$，该值要么为 $0$，要么为 $1$。

对于每种大小 $k$（$1 \le k \le n$），请确定：通过选取满足下列条件的顶点集合 $S$，能够获得哪些异或值：

• $|S| = k$；
• 若顶点 $v$ 属于集合 $S$，则顶点 $v$ 的子树中的所有顶点也一定属于 $S$。

集合 $S$ 的值定义为该集合中所有顶点的值的异或： $\bigoplus_{v \in S} a_v.$

顶点 $v$ 的子树是指所有满足如下条件的顶点 $u$ 构成的集合：从根 $1$ 到顶点 $u$ 的简单路径经过顶点 $v$。

比特的异或运算定义如下： $0 \oplus 0 = 0$， $0 \oplus 1 = 1$， $1 \oplus 0 = 1$， $1 \oplus 1 = 0$。

顶点 $v$ 的子顶点是指其父顶点为 $v$ 的顶点。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 1000$）—— 测试数据的组数。

每组测试数据由三行组成。

每组数据的第一行包含一个整数 $n$（$2 \le n \le 4 \cdot 10^5$）—— 树中顶点的个数。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$a_i \in \{0, 1\}$）—— 各个顶点的值。

第三行包含 $n-1$ 个整数 $p_2, p_3, \ldots, p_n$（$1 \le p_i < i$），其中 $p_i$ 是顶点 $i$ 的父顶点。

保证所有测试数据的 $n$ 之和不超过 $4 \cdot 10^5$。

输出格式

对于每组测试数据，输出一行包含 $n$ 个整数 $ans_1, ans_2, \ldots, ans_n$。

对于每个 $k$：

• $ans_k = 0$，若在所有大小为 $k$ 的合法集合中，只能得到异或值 $0$；
• $ans_k = 1$，若在所有大小为 $k$ 的合法集合中，只能得到异或值 $1$；
• $ans_k = 2$，若在所有大小为 $k$ 的合法集合中，既能得到异或值 $0$，也能得到异或值 $1$。

输入输出样例 #1

输入 #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 

说明/提示

下面分别是第一个和第二个测试用例中的树的形态。

:::align{center} :::

考虑第一个测试用例。

对于 $k = 1$，两种异或值都可以得到。例如，集合 $S = \{5\}$ 是合法的且异或值为 $0$。集合 $S = \{3\}$ 也是合法的且异或值为 $1$。因此 $ans_1 = 2$。

对于 $k = 3$，两种异或值也都可以得到。例如，集合 $S = \{2, 3, 5\}$ 是合法的，因为顶点 $2$ 与其子树中的所有顶点一同被选中。它的异或值为 $a_2 \oplus a_3 \oplus a_5 = 0 \oplus 1 \oplus 0 = 1$。而集合 $S = \{3, 4, 5\}$ 也是合法的，因为顶点 $4$ 与其子树中的所有顶点一同被选中。它的异或值为 $a_3 \oplus a_4 \oplus a_5 = 1 \oplus 1 \oplus 0 = 0$。因此 $ans_3 = 2$。

所以，第一个测试用例的答案为 $2\ 1\ 2\ 0\ 1$。

考虑第二个测试用例。

在此测试用例中，仅当 $k = 6$ 时两种异或值都能得到。

例如，集合 $S = \{3, 4, 6, 7, 8, 9\}$ 是合法的。它的异或值为 $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$。

而集合 $S = \{4, 5, 6, 7, 8, 9\}$ 也是合法的。它的异或值为 $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$。因此 $ans_6 = 2$。

所以，第二个测试用例的答案为 $1\ 0\ 1\ 0\ 1\ 2\ 0\ 0\ 0$。

计分

叶子是指没有子顶点的顶点。

竹子是指每个顶点至多有一个子顶点的树。

• （$2$ 分）：$\sum n \le 20$；
• （$3$ 分）：$p_i=1$；
• （$5$ 分）：$\sum n^3 \le 10^8$；
• （$8$ 分）：$\sum n^2 \le 10^8$；
• （$12$ 分）：所有测试用例中叶子总数不超过 $100$；
• （$8$ 分）：去掉顶点 $1$ 后，每个连通分量均为竹子，且这样的连通分量至多有两个；
• （$9$ 分）：去掉顶点 $1$ 后，每个连通分量均为竹子；
• （$9$ 分）：所有树都是满二叉树，即存在整数 $q$ 使得 $n = 2^q - 1$，且对每个顶点 $i > 1$ 有 $p_i = \left\lfloor \frac{i}{2} \right\rfloor$；
• （$22$ 分）：每个测试用例满足 $n \le 2 \cdot 10^5$；
• （$22$ 分）：无额外限制。

翻译由 DeepSeek V4 Pro 完成