void solve() {
    const int n = 30000;
    vector<int> f(n + 1), w(n + 1), sz(n + 1);
    for (int i = 1; i <= n; i++) f[i] = i, w[i] = 0, sz[i] = 1;

    function<pair<int, int>(int)> find = [&] (int u)->pii {
        if (u == f[u]) {
            return {u, 0};
        }
        auto [root, wfather] = find(f[u]);
        f[u] = root;
        w[u] = wfather + w[u];
        return {root, w[u]};
    };

    auto merge = [&] (int u, int v) {
        auto [fu, lenu] = find(u);
        auto [fv, lenv] = find(v);
        if (fu == fv) return;
        f[fu] = fv;
        w[fu] = sz[fv];
        sz[fv] += sz[fu];
    };

    auto query = [&] (int u, int v) {
        auto [fu, lenu] = find(u);
        auto [fv, lenv] = find(v);
        if (fu != fv) return -1;
        return abs(lenu - lenv) - 1;
    };
    int m;
    cin >> m;
    while (m--) {
        char o;
        int x, y;
        cin >> o >> x >> y;
        if (o == 'M') {
            merge(x, y);
        } else {
            cout << query(x, y) << '\n';
        }
    }
}

0 条评论

目前还没有评论...

信息

ID
426
时间
ms
内存
MiB
难度
5
标签
递交数
19
已通过
14
上传者