CF1900C.Anji's Binary Tree

Keksic keeps getting left on seen by Anji. Through a mutual friend, he's figured out that Anji really likes binary trees and decided to solve her problem in order to get her attention.

Anji has given Keksic a binary tree with $n$ vertices. Vertex $1$ is the root and does not have a parent. All other vertices have exactly one parent. Each vertex can have up to $2$ children, a left child, and a right child. For each vertex, Anji tells Keksic index of both its left and its right child or tells him that they do not exist.

Additionally, each of the vertices has a letter $s_i$ on it, which is either 'U', 'L' or 'R'.

Keksic begins his journey on the root, and in each move he does the following:

• If the letter on his current vertex is 'U', he moves to its parent. If it doesn't exist, he does nothing.
• If the letter on his current vertex is 'L', he moves to its left child. If it doesn't exist, he does nothing.
• If the letter on his current vertex is 'R', he moves to its right child. If it doesn't exist, he does nothing.

Before his journey, he can perform the following operations: choose any node, and replace the letter written on it with another one.

You are interested in the minimal number of operations he needs to do before his journey, such that when he starts his journey, he will reach a leaf at some point. A leaf is a vertex that has no children. It does not matter which leaf he reaches. Note that it does not matter whether he will stay in the leaf, he just needs to move to it. Additionally, note that it does not matter how many times he needs to move before reaching a leaf.

Help Keksic solve Anji's tree so that he can win her heart, and make her come to Čačak.

凯克西奇总是被安吉标记为“已读”。通过一位共同的朋友，他得知安吉特别喜欢二叉树，于是决定解决她出的一道题，以引起她的注意。

安吉给了凯克西奇一棵含 $n$ 个顶点的二叉树。顶点 $1$ 是根节点，没有父节点；其余每个顶点恰好有一个父节点。每个顶点最多有两个子节点：一个左子节点和一个右子节点。对于每个顶点，安吉会告诉凯克西奇其左子节点和右子节点的编号（若不存在，则明确告知不存在）。

此外，每个顶点上标有一个字母 $s_i$，该字母为 'U'、'L' 或 'R' 之一。

凯克西奇从根节点出发，每次移动按如下规则进行：

• 若当前顶点上的字母为 'U'，则他移动到其父节点；若父节点不存在，则不执行任何操作；
• 若当前顶点上的字母为 'L'，则他移动到其左子节点；若左子节点不存在，则不执行任何操作；
• 若当前顶点上的字母为 'R'，则他移动到其右子节点；若右子节点不存在，则不执行任何操作。

在开始旅程前，他可以执行如下操作：任选一个节点，并将其上的字母替换为另外两个字母中的任意一个（即 'U'、'L'、'R' 中的另一个）。

你关心的是：他需要在旅程开始前执行的最少操作次数，使得当他启动旅程后，在某一步中能到达某个叶节点。叶节点是指没有子节点的顶点（即既无左子节点也无右子节点）。到达哪一个叶节点并不重要。注意：他只需抵达叶节点即可（不必停留在叶节点），且到达所需步数也无关紧要。

请帮助凯克西奇解开安吉的这棵二叉树，助他赢得芳心，让她来到查查克。

Each test consists of multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 5 \cdot 10^4$) — the number of test cases. The description of test cases follows.

The first line of each test case contains a single integer $n$ ($2 \le n \le 3 \cdot 10^5$) — the number of vertices in a tree.

The second line of each test case contains a string $s$ of $n$ characters — characters are written on the vertices. It is guaranteed that $s$ consists only of characters 'U', 'L', and 'R'.

The $i$-th of the next $n$ lines contains two integers $l_i$ and $r_i$ ($0 \le l_i, r_i \le n$) — indices of left and right child of the vertex $i$. If $l_i = 0$, it means that vertex $i$ does not have a left child. If $r_i = 0$, it means that vertex $i$ does not have a right child. It is guaranteed that this data describes a valid binary tree rooted at $1$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $3 \cdot 10^5$.

每个测试包含多个测试用例。第一行包含一个整数 $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$。

For each test case, output a single integer — the minimal number of operations Keksic needs to do to reach a leaf.

对于每个测试用例，输出一个整数——Keksic 到达叶子节点所需的最少操作次数。

In the first test case, vertex $1$ has $2$ as its left child and $3$ as its right child. Vertices $2$ and $3$ do not have children and are therefore leaves. As 'L' is written on vertex $1$, Keksic will go to vertex $2$, therefore he has to do no operations.

In the second test case, vertex $1$ has $3$ as its left child and $2$ as its right child. Vertices $2$ and $3$ are leaves. As 'U' is written on vertex $1$, Keksic needs to change it to either 'L' or 'R' in order for him to reach a leaf.

In the third case, vertex $1$ has only a right child, which is vertex $2$. As 'L' is written on it, Keksic needs to change it to 'R', otherwise he would be stuck on vertex $1$.

In the fourth case, he can change $3$ characters so that letters on the vertices are "LURL", which makes him reach vertex $2$.

In the fifth case, there are $3$ leaves, $3$, $6$ and $7$. To reach either leaf $6$ or leaf $7$, he needs to change $2$ characters. However, if he changes character on vertex $1$ to 'R', he will reach leaf $3$, therefore the answer is $1$.

The initial tree in test case 5.

在第一个测试用例中，顶点 $1$ 的左子节点为 $2$，右子节点为 $3$。顶点 $2$ 和 $3$ 均无子节点，因此均为叶子节点。由于顶点 $1$ 上标记为 'L'，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 中的初始树。