← 返回题目列表

Codeforces · 1900/C

C. 安吉的二叉树

中文机器翻译题面 查看原题

Keksic 总是被安吉看到。通过共同的朋友,他发现安吉真的很喜欢二叉树,并决定解决她的问题以引起她的注意。

Anji 给了 Keksic 一棵带有 $$$n$$$ 顶点的二叉树。顶点 $$$1$$$ 是根,没有父节点。所有其他顶点都只有一个父顶点。每个顶点最多可以有 $$$2$$$ 个子节点、一个左子节点和一个右子节点。对于每个顶点,Anji 告诉 Keksic 其左子节点和右子节点的索引,或者告诉他它们不存在。

此外,每个顶点上都有一个字母 $$$s_i$$$,即“U”、“L”或“R”。

Keksic 从根部开始他的旅程,在每一步中他都会执行以下操作:

- 如果当前顶点上的字母是“U”,则他将移动到其父顶点。如果它不存在,他什么也不做。
- 如果当前顶点上的字母是“L”,则他移动到其左子节点。如果它不存在,他什么也不做。
- 如果当前顶点上的字母是“R”,则他移动到其右子节点。如果它不存在,他什么也不做。

您对他在旅程之前需要执行的最少操作感兴趣,这样当他开始旅程时,他会在某个时刻到达一片叶子。叶子是没有子节点的顶点。他到达哪一片叶子并不重要。请注意,他是否留在叶子中并不重要,他只需要移动到叶子处即可。此外,请注意,在到达树叶之前他需要移动多少次并不重要。

帮助Keksic解决Anji的树,这样他就可以赢得她的心,并让她来到查查克。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 5 \cdot 10^4$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 3 \cdot 10^5$$$) — 树中的顶点数。

每个测试用例的第二行包含一个由 $$$n$$$ 个字符组成的字符串 $$$s$$$ — 字符写在顶点上。保证 $$$s$$$ 仅包含字符“U”、“L”和“R”。

接下来的 $$$n$$$ 行的第 $$$i$$$ 包含两个整数 $$$l_i$$$ 和 $$$r_i$$$ ($$$0 \le l_i, r_i \le n$$$) - 顶点 $$$i$$$ 的左子节点和右子节点的索引。如果$$$l_i = 0$$$,则意味着顶点$$$i$$$没有左子节点。如果$$$r_i = 0$$$,则意味着顶点$$$i$$$没有右子节点。保证该数据描述以$$$1$$$为根的有效二叉树。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$3 \cdot 10^5$$$。

输出

对于每个测试用例,输出一个整数 - Keksic 到达叶子所需执行的最少操作数。

示例

输入 #1

5
3
LRU
2 3
0 0
0 0
3
ULR
3 2
0 0
0 0
2
LU
0 2
0 0
4
RULR
3 0
0 0
0 4
2 0
7
LLRRRLU
5 2
3 6
0 0
7 0
4 0
0 0
0 0

输出 #1

0
1
1
3
1

注意

在第一个测试用例中,顶点 $$$1$$$ 将 $$$2$$$ 作为其左子节点,将 $$$3$$$ 作为其右子节点。顶点 $$$2$$$ 和 $$$3$$$ 没有子节点,因此是叶子。由于“L”写在顶点$$$1$$$上,Keksic将前往顶点$$$2$$$,因此他不必执行任何操作。

在第二个测试用例中,顶点 $$$1$$$ 将 $$$3$$$ 作为其左子节点,将 $$$2$$$ 作为其右子节点。顶点 $$$2$$$ 和 $$$3$$$ 是叶子。由于顶点 $$$1$$$ 上写有“U”,Keksic 需要将其更改为“L”或“R”才能到达叶子。

在第三种情况下,顶点 $$$1$$$ 只有一个右子节点,即顶点 $$$2$$$。由于上面写的是“L”,Keksic 需要将其更改为“R”,否则他会卡在顶点 $$$1$$$ 上。

在第四种情况下,他可以更改$$$3$$$字符,使顶点上的字母为“LURL”,这使他到达顶点$$$2$$$。

在第五种情况中,有$$$3$$$叶子、$$$3$$$、$$$6$$$和$$$7$$$。要到达叶子 $$$6$$$ 或叶子 $$$7$$$,他需要更改 $$$2$$$ 字符。然而,如果他将顶点 $$$1$$$ 上的字符更改为“R”,他将到达叶子 $$$3$$$,因此答案是 $$$1$$$。

测试用例 5 中的初始树。