luogu#P7732. [JDWOI-2] 红黑树

[JDWOI-2] 红黑树

题目背景

小 M 迷上了画画,所以她用红色和黑色的画笔画出了一棵红黑树。

题目描述

这棵树有 nn 个点,从 11 开始标号,其中 11 号点为树根。一开始,小 M 给这 nn 个点分别涂上了红色或黑色,第 ii 号点的颜色是 aia_i('R' 代表红色,'B' 代表黑色)。

但可惜的是,小 M 对这棵树并不是非常满意,她希望第 ii 号点的颜色为 bib_i

好在她的好朋友小 K 懂得一点点膜法。小 K 可以先选定一个点,然后把这个点的颜色反转(红变黑,黑变红)。但这个膜法太强大了,所以会把膜法传递下去,即在反转的一秒之后使当前点的父节点颜色也进行反转,如此传递,直到根节点为止。特殊的,如果在同一时刻有多个膜法作用在同一个点上,这些膜法会两两抵消,如果恰好抵消完了(即膜法的个数为偶数),则当前点不会变色,并且不会有膜法继续传递下去。注意此处抵消膜法不需要耗时间。

但毕竟小 K 还是个新手,所以他在一秒之内只能最多对一个节点施展上述膜法。

为了尽快让小 M 开心,小 K 想知道,至少经过多少秒才能让这棵红黑树初次出现小 M 的理想颜色状态?可以证明,总可以按题目要求变成理想颜色状态。

输入格式

本题多测

第一行一个整数 QQ,表示数据组数。

对于每组数据:

第一行一个整数 nn,表示红黑树的节点数。

第二行一个长度为 nn 的字符串 aa,表示红黑树的初始颜色状态,其中仅含有 'R' 或 'B'。

接下来 n1n-1 行,每行两个整数 x,yx,y,描述一条树边。

最后一行一个长度为 nn 的字符串 bb,表示红黑树的理想颜色状态,其中仅含有 'R' 或 'B'。

输出格式

QQ 行每行一个整数,一组数据一行,表示答案,即最小耗时。

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 可以在第 11 秒给 44 号点膜法,整个树变为 RRBRR,在第 22 秒给 55 号点膜法,整个树变成 RBBRB,在第 33 秒给 11 号点膜法,整个树变成 BRBRB。

第二组数据中,小 K 可以在第 11 秒给 55 号点膜法,在第二秒给 22 号点膜法;或者在第 11 秒给 33 号点膜法,在第 22 秒给 55 号点膜法。

【数据范围】

对于 10%10\% 的数据,1n51\leq n\leq 5

对于 30%30\% 的数据,1n101\leq n\leq 10

对于另外 20%20\% 的数据,aibi\forall a_i\neq b_i

对于 100%100\% 的数据,1n201\leq n\leq 201Q201\leq Q\leq 20,树随机生成。