#P18449. Red Black Tree

Red Black Tree

Red Black Tree

给定一棵有 nn 个顶点的有根树,顶点编号为 11 到 nn,根为顶点 11。每个顶点为红色或黑色。

若从某个顶点出发,到它的任意后代叶子的简单路径上,黑色顶点数量均相同,则称这个顶点是好点。若一棵树的所有顶点都是好点,则称这棵树是完美的。这里路径包含起点和终点。

记 RkR_k 为以顶点 kk 为根的子树。对每个 1≤k≤n1\le k\le n,分别回答:可以选择一些顶点并翻转它们的颜色(红变黑、黑变红),为了使 RkR_k 完美,最少需要选择多少个顶点?

简单路径不会重复经过同一条边。以 kk 为根的子树由 kk 的全部后代组成,根为 kk;每个点也是它自己的后代。各个子树的问题分别独立求最小值。

输入格式

输入包含多个测试实例。第一行一个整数 TT,表示测试实例数。每个实例:

第一行一个整数 nn,满足 2≤n≤1052\le n\le10^5,表示顶点数。

第二行一个长度为 nn 的字符串 s1s2⋯sns_1s_2\cdots s_n,其中 si∈{0,1}s_i\in\{0,1\}。si=0s_i=0 表示顶点 ii 为红色,si=1s_i=1 表示黑色。

第三行 n−1n-1 个整数 p2,p3,…,pnp_2,p_3,\ldots,p_n,满足 1≤pi<i1\le p_i<i,其中 pip_i 是顶点 ii 的父亲。

保证全部测试实例的 nn 之和不超过 10610^6。

输出格式

每个测试实例输出一行 nn 个整数,以单个空格分隔。第 ii 个整数表示使 RiR_i 完美所需翻转的最少顶点数。

请勿在每行末尾输出多余空格,否则可能被判为错误。

样例

2
9
101011110
1 1 3 3 3 6 2 2
4
1011
1 1 3
4 1 2 0 0 0 0 0 0
2 0 0 0

样例说明

第一个测试实例的原树如下,红色表示红点、黑色表示黑点:

第一个原样例的有根树

为了使 R1R_1 完美,可以翻转顶点 2,4,6,92,4,6,9。之后从顶点 11 到任意后代叶子的路径都包含 33 个黑色顶点;从顶点 22 到任意后代叶子的路径包含 22 个黑色顶点,从顶点 33 到任意后代叶子的路径也包含 22 个黑色顶点。顶点 44 到 99 都只有一个后代叶子,因而总是好点。

为了使 R2R_2 完美,可以翻转顶点 88。之后从顶点 22 到任意后代叶子的路径均含 00 个黑色顶点。顶点 8,98,9 各只有一个后代叶子,因而总是好点。

原英文说明此处误写为“0 vertices”;由原定义、原颜色及翻转 88 后全红的路径可确认指“0 black vertices”。本题未改变定义或答案。