#P18449. Red Black Tree
Red Black Tree
Red Black Tree
给定一棵有 个顶点的有根树,顶点编号为 到 ,根为顶点 。每个顶点为红色或黑色。
若从某个顶点出发,到它的任意后代叶子的简单路径上,黑色顶点数量均相同,则称这个顶点是好点。若一棵树的所有顶点都是好点,则称这棵树是完美的。这里路径包含起点和终点。
记 为以顶点 为根的子树。对每个 ,分别回答:可以选择一些顶点并翻转它们的颜色(红变黑、黑变红),为了使 完美,最少需要选择多少个顶点?
简单路径不会重复经过同一条边。以 为根的子树由 的全部后代组成,根为 ;每个点也是它自己的后代。各个子树的问题分别独立求最小值。
输入格式
输入包含多个测试实例。第一行一个整数 ,表示测试实例数。每个实例:
第一行一个整数 ,满足 ,表示顶点数。
第二行一个长度为 的字符串 ,其中 。 表示顶点 为红色, 表示黑色。
第三行 个整数 ,满足 ,其中 是顶点 的父亲。
保证全部测试实例的 之和不超过 。
输出格式
每个测试实例输出一行 个整数,以单个空格分隔。第 个整数表示使 完美所需翻转的最少顶点数。
请勿在每行末尾输出多余空格,否则可能被判为错误。
样例
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
样例说明
第一个测试实例的原树如下,红色表示红点、黑色表示黑点:

为了使 完美,可以翻转顶点 。之后从顶点 到任意后代叶子的路径都包含 个黑色顶点;从顶点 到任意后代叶子的路径包含 个黑色顶点,从顶点 到任意后代叶子的路径也包含 个黑色顶点。顶点 到 都只有一个后代叶子,因而总是好点。
为了使 完美,可以翻转顶点 。之后从顶点 到任意后代叶子的路径均含 个黑色顶点。顶点 各只有一个后代叶子,因而总是好点。
原英文说明此处误写为“0 vertices”;由原定义、原颜色及翻转 后全红的路径可确认指“0 black vertices”。本题未改变定义或答案。