luogu#P7732. [JDWOI-2] 红黑树
[JDWOI-2] 红黑树
题目背景
小 M 迷上了画画,所以她用红色和黑色的画笔画出了一棵红黑树。
题目描述
这棵树有 个点,从 开始标号,其中 号点为树根。一开始,小 M 给这 个点分别涂上了红色或黑色,第 号点的颜色是 ('R' 代表红色,'B' 代表黑色)。
但可惜的是,小 M 对这棵树并不是非常满意,她希望第 号点的颜色为 。
好在她的好朋友小 K 懂得一点点膜法。小 K 可以先选定一个点,然后把这个点的颜色反转(红变黑,黑变红)。但这个膜法太强大了,所以会把膜法传递下去,即在反转的一秒之后使当前点的父节点颜色也进行反转,如此传递,直到根节点为止。特殊的,如果在同一时刻有多个膜法作用在同一个点上,这些膜法会两两抵消,如果恰好抵消完了(即膜法的个数为偶数),则当前点不会变色,并且不会有膜法继续传递下去。注意此处抵消膜法不需要耗时间。
但毕竟小 K 还是个新手,所以他在一秒之内只能最多对一个节点施展上述膜法。
为了尽快让小 M 开心,小 K 想知道,至少经过多少秒才能让这棵红黑树初次出现小 M 的理想颜色状态?可以证明,总可以按题目要求变成理想颜色状态。
输入格式
本题多测。
第一行一个整数 ,表示数据组数。
对于每组数据:
第一行一个整数 ,表示红黑树的节点数。
第二行一个长度为 的字符串 ,表示红黑树的初始颜色状态,其中仅含有 'R' 或 'B'。
接下来 行,每行两个整数 ,描述一条树边。
最后一行一个长度为 的字符串 ,表示红黑树的理想颜色状态,其中仅含有 'R' 或 'B'。
输出格式
共 行每行一个整数,一组数据一行,表示答案,即最小耗时。
2
5
RRBBR
1 2
1 3
2 4
2 5
BRBRB
5
RRRRR
1 2
2 3
3 4
4 5
BBBBB
3
3
提示
【样例解释】
第一组数据中,小 K 可以在第 秒给 号点膜法,整个树变为 RRBRR,在第 秒给 号点膜法,整个树变成 RBBRB,在第 秒给 号点膜法,整个树变成 BRBRB。
第二组数据中,小 K 可以在第 秒给 号点膜法,在第二秒给 号点膜法;或者在第 秒给 号点膜法,在第 秒给 号点膜法。
【数据范围】
对于 的数据,;
对于 的数据,;
对于另外 的数据,;
对于 的数据,,,树随机生成。