P16459 [UOI 2026] Tree Subsets

给定一棵有 $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$。

下面分别是第一个和第二个测试用例中的树的形态。 :::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 完成