P13954 [ICPC 2023 Nanjing R] 红黑树

有一棵 $n$ 个节点的有根树，节点编号从 $1$ 到 $n$，其中节点 $1$ 为根。每个节点都有一个颜色， 要么是红色，要么是黑色。 称一个节点是好的，若每一条以该节点为起点，以该节点任意一个后代叶子节点为终点的简单路径中，都包含相同数量的黑色节点。称一棵树是完美的，若树中每个节点都是好的。 令 $R_k$ 表示以节点 $k$ 为根的子树。对于每个 $1 \le k \le n$，回答以下询问：如果您可以任意选择一些节点并改变它们的颜色（也就是说，把红色节点改成黑色，以及把黑色节点改成红色），至少需要选择几个节点才能让 $R_k$ 变得完美。 请回忆：简单路径不会多次经过同一条边。 同时请回忆：以节点 $k$ 为根的子树是一棵由节点 $k$ 所有后代组成的有根树，并以节点 $k$ 为根。请注意，每个节点都是它自己的后代。

有多组测试数据。第一行输入一个整数 $T$ 表示测试数据组数，对于每组测试数据： 第一行输入一个整数 $n$（$2 \le n \le 10^5$）表示树中节点的数量。 第二行输入一个长度为 $n$ 的字符串 $s_1s_2\cdots s_n$（$s_i \in \{0, 1\}$）。若 $s_i = 0$ 则节点 $i$ 是红色节点；若 $s_i = 1$ 则节点 $i$ 是黑色节点。 第三行输入 $(n - 1)$ 个整数 $p_2, p_3, \cdots, p_n$（$1 \le p_i < i$），其中 $p_i$ 是节点 $i$ 的父节点。 保证所有数据 $n$ 之和不超过 $10^6$。

每组数据输出一行 $n$ 个由单个空格分隔的整数，其中第 $i$ 个整数表示至少需要选择几个节点才能让 $R_i$ 变得完美。 请不要在行末输出多余空格，否则您的答案可能会被认为是错误的！

:::align{center}  ::: 我们展示第一组样例数据。 为了让 $R_1$ 变得完美，我们可以改变节点 $2$，$4$，$6$ 和 $9$ 的颜色。改变之后，所有从节点 $1$ 到后代叶子节点的路径均包含 $3$ 个黑色节点，所有从节点 $2$ 到后代叶子节点的路径均包含 $2$ 个黑色节点，所有从节点 $3$ 到后代叶子节点的路径均包含 $2$ 个黑色节点。由于节点 $4$ 到 $9$ 都只有一个后代叶子节点，所以它们一直都是好的。 为了让 $R_2$ 变得完美，我们可以改变节点 $8$ 的颜色。改变之后，所有从节点 $2$ 到后代叶子节点的路径均包含 $0$ 个黑色节点。由于节点 $8$ 和 $9$ 都只有一个后代叶子节点，所以它们一直都是好的。