rt，想法是 U 所在的连通块所有节点都是 U

第三个大样例

输出

0
0
101
14
270
893

答案

0
0
206
15
275
891

代码

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10;
int n,m,fa[MAXN];
bitset<MAXN> isu,vis;
basic_string<int> p[MAXN];

void init() {
    cin >> n >> m;
    isu.reset();
    vis.reset();
    memset(fa,0,sizeof fa);
    for(int i = 1;i <= n;i++) p[i].clear();
    for(int i,j;m;m--){
        char v;
        cin >> v >> i;
        if(v == 'U'){
            fa[i] = i,isu[i] = 1;
        } else {
            cin >> j;
            fa[i] = j,isu[i] = 0;
        }
    }
    for(int u = 1;u <= n;u++) p[u] += fa[u],p[fa[u]] += u;
}

int dfs(int u){
    if(vis[u]) return 0;
    int res = vis[u] = 1;
    for(int v : p[u]) res += dfs(v);
    return res;
}

void solve(){
    init();
    int ans = 0;
    for(int u = 1;u <= n;u++){
        if(vis[u] || !isu[u]) continue;
        ans += dfs(u);
    }
    cout << ans << '\n';
}

int main() { 
    int c,t;
    cin >> c >> t;
    while(t--) solve();
}