题目描述

难度分:$1300$

输入$T(\leq 5 \times 10^4)$表示$T$组数据。所有数据的$n$之和$\leq 3 \times 10^5$。

每组数据输入$n(2 \leq n \leq 3 \times 10^5)$和一个长为$n$的字符串$s$，只包含U、L、R三种字母。

然后输入$n$对整数$L[i]$和$R[i]$，表示一棵$n$个节点的二叉树，第$i$个节点的左儿子和右儿子的节点编号分别为$L[i]$和$R[i]$。

节点编号从$1$到$n$。如果$L[i]=0$表示$i$没有左儿子，如果$R[i]=0$表示$i$没有右儿子。

每个节点$i$都有一个指令$s[i]$，表示往父节点（U），左儿子（L），右儿子（R）方向移动。如果指令对应的节点不存在，则原地不动。

你可以修改$s$中的字母。至少要修改多少次，使得我们能从根节点$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

输出样例

0
1
1
3
1

算法

BFS求最短路

按照以下规则在读入$L$和$R$的数据时建图，$0$表示不需要修改指令，$1$表示需要修改指令：

1. 如果$i$节点上的指令是L，那么它到左孩子的边权为$0$，到其他邻居节点的边权为$1$。
2. 如果$i$节点上的指令是R，那么它到右孩子的边权为$0$，到其他邻居节点的边权为$1$。
3. 如果$i$节点上的指令是U，那么它到父节点的边权为$0$，到其他邻居节点的边权为$1$。

在建图的过程中将所有叶子节点编号存入到一个$leaves$数组中，然后从$1$开始进行BFS。最后遍历$leaves$数组中的节点编号，$1$到这些叶子节点的最短路的最小值就是答案。

复杂度分析

时间复杂度

输入$L[i]$和$R[i]$的时候建图，从节点$1$开始做一遍BFS就结束了，时间复杂度为$O(n)$。

空间复杂度

由于整个图是一棵树，空间复杂度为$O(n)$。在BFS的过程中需要$dist$数组和去重数组$st$，它们的空间消耗也是线性的。因此，整个算法的额外空间复杂度为$O(n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> PII;

const int N = 300010, INF = 0x3f3f3f3f;
char s[N];
int t, n, dist[N];
bool st[N];
vector<PII> graph[N];

int main() {
    scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);
        scanf("%s", s + 1);
        for(int i = 1; i <= n; i++) {
            graph[i].clear();
            st[i] = false;
            dist[i] = INF;
        }
        vector<int> leaves;
        for(int i = 1; i <= n; i++) {
            int l, r;
            scanf("%d%d", &l, &r);
            if(l) {
                if(s[i] == 'L') {
                    graph[i].push_back({l, 0});
                }else {
                    graph[i].push_back({l, 1});
                }
                if(s[l] == 'U') {
                    graph[l].push_back({i, 0});
                }else {
                    graph[l].push_back({i, 1});
                }
            }
            if(r) {
                if(s[i] == 'R') {
                    graph[i].push_back({r, 0});
                }else {
                    graph[i].push_back({r, 1});
                }
                if(s[r] == 'U') {
                    graph[r].push_back({i, 0});
                }else {
                    graph[r].push_back({i, 1});
                }
            }
            if(!l && !r) leaves.push_back(i);
        }
        priority_queue<PII, vector<PII>, greater<PII>> q;
        dist[1] = 0;
        q.push({dist[1], 1});
        while(!q.empty()) {
            auto tup = q.top();
            q.pop();
            int cur = tup.second;
            if(st[cur]) continue;
            st[cur] = true;
            for(auto&pir: graph[cur]) {
                int nxt = pir.first, w = pir.second;
                if(dist[nxt] > dist[cur] + w) {
                    dist[nxt] = dist[cur] + w;
                    q.push({dist[nxt], nxt});
                }
            }
        }
        int ans = INF;
        for(int x: leaves) {
            ans = min(ans, dist[x]);
        }
        printf("%d\n", ans);
    }
    return 0;
}