带权并查集

看错题了，wa了好几发

#include <bits/stdc++.h>

using i64 = long long;

struct DSU
{
    std::vector<int> f, siz, d;
    DSU(int n) : f(n), siz(n, 1), d(n, 0)
    {
        std::iota(f.begin(), f.end(), 0);
    }
    int leader(int x)
    {
        if (x != f[x])
        {
            int tmp = f[x];
            f[x] = leader(f[x]);
            d[x] += d[tmp];
        }
        return f[x];
    }
    bool same(int x, int y)
    {
        return leader(x) == leader(y);
    }
    void merge(int x, int y)
    {
        x = leader(x), y = leader(y);
        if (x != y)
        {
            f[x] = y;
            d[x] += siz[y];
            siz[y] += siz[x];
        }
    }
    int size(int x)
    {
        return siz[leader(x)];
    }
};

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int T;
    std::cin >> T;

    DSU dsu(30010);

    while (T--)
    {
        char op;
        int i, j;
        std::cin >> op >> i >> j;
        i--, j--;

        if (op == 'M')
        {
            dsu.merge(i, j);
        }
        else
        {
            if (dsu.same(i, j))
                std::cout << std::max(0, std::abs(dsu.d[j] - dsu.d[i]) - 1) << '\n';
            else
                std::cout << "-1\n";
        }
    }

    return 0;
}

#include <bits/stdc++.h>
using namespace std;

const int N = 200010;

int n, m;
int p[N];
unordered_map<int, int> S;

struct Query
{
    int x, y, e;
} query[N];

int get(int x)
{
    if (S.count(x) == 0)
        S[x] = ++n;
    return S[x];
}

int find(int x)
{
    if (p[x] != x)
        p[x] = find(p[x]);
    return p[x];
}

void solve()
{
    n = 0;
    S.clear();
    scanf("%d", &m);
    for (int i = 0; i < m; i++)
    {
        int x, y, e;
        scanf("%d%d%d", &x, &y, &e);
        query[i] = {get(x), get(y), e};
    }

    for (int i = 1; i <= n; i++)
        p[i] = i;

    for (int i = 0; i < m; i++)
        if (query[i].e == 1)
        {
            int pa = find(query[i].x), pb = find(query[i].y);
            p[pa] = pb;
        }

    bool has_conflict = false;
    for (int i = 0; i < m; i++)
        if (query[i].e == 0)
        {
            int pa = find(query[i].x), pb = find(query[i].y);
            if (pa == pb)
            {
                has_conflict = true;
                break;
            }
        }

    std::cout << (has_conflict ? "NO\n" : "YES\n");
}

int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        solve();
    }

    return 0;
}

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3, "Ofast", "inline")

#include <bits/stdc++.h>

using i64 = long long;

struct DSU
{
    std::vector<int> f, siz;
    DSU(int n) : f(n), siz(n, 1)
    {
        std::iota(f.begin(), f.end(), 0);
    }
    int leader(int x)
    {
        return x == f[x] ? x : f[x] = leader(f[x]);
    }
    bool same(int x, int y)
    {
        return leader(x) == leader(y);
    }
    void merge(int x, int y)
    {
        x = leader(x), y = leader(y);
        if (x != y)
        {
            siz[x] += siz[y];
            f[y] = x;
        }
    }
    int size(int x)
    {
        return siz[leader(x)];
    }
};

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, k, m;
    std::cin >> n >> k >> m;

    std::vector<int> v(n), w(n);
    for (int i = 0; i < n; i++)
        std::cin >> v[i] >> w[i];

    DSU dsu(n);
    while (k--)
    {
        int a, b;
        std::cin >> a >> b;
        a--, b--;
        dsu.merge(a, b);
    }

    for (int i = 0; i < n; i++)
    {
        int fa = dsu.leader(i);
        if (fa == i)
            continue;
        v[fa] += v[i], w[fa] += w[i];
    }

    std::vector<int> f(m + 1);
    for (int i = 0; i < n; i++)
        if (dsu.leader(i) == i)
            for (int j = m; j >= v[i]; j--)
                f[j] = std::max(f[j], f[j - v[i]] + w[i]);
    std::cout << f[m] << '\n';
    return 0;
}

#include <bits/stdc++.h>

using i64 = long long;

struct DSU
{
    std::vector<int> f, siz;
    DSU(int n) : f(n), siz(n, 1) { std::iota(f.begin(), f.end(), 0); }
    int leader(int x)
    {
        return x == f[x] ? x : f[x] = leader(f[x]);
    }
    bool same(int x, int y)
    {
        return leader(x) == leader(y);
    }
    void merge(int x, int y)
    {
        x = leader(x), y = leader(y);
        if (x != y)
        {
            siz[y] += siz[x];
            f[x] = y;
        }
    }
    int size(int x)
    {
        return siz[leader(x)];
    }
};

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, m;
    std::cin >> n >> m;

    DSU dsu(n * n);

    for (int i = 1; i <= m; i++)
    {
        char op;
        int a, b;
        std::cin >> a >> b >> op;
        a--, b--;
        int x = a * n + b, y;
        if (op == 'D')
            y = (a + 1) * n + b;
        else
            y = a * n + b + 1;
        if (dsu.same(x, y))
        {
            std::cout << i << '\n';
            return 0;
        }
        dsu.merge(x, y);
    }
    std::cout << "draw\n";

    return 0;
}

#include <bits/stdc++.h>

using i64 = long long;

template <typename T>
struct Fenwick
{
    const int n;
    std::vector<int> t;
    Fenwick(int n) : n(n), t(n + 1) {}
    void add(int x, T c)
    {
        for (int i = x; i <= n; i += i & -i)
            t[i] += c;
    }
    T sum(int x)
    {
        T res = 0;
        for (int i = x; i; i -= i & -i)
            res += t[i];
        return res;
    }
};

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    std::cin >> n;

    Fenwick<int> fen(n);

    std::vector<int> a(n + 1);
    for (int i = 2; i <= n; i++)
        std::cin >> a[i];

    for (int i = 1; i <= n; i++)
        fen.add(i, 1);

    std::vector<int> res(n + 1);
    for (int i = n; i >= 1; i--)
    {
        int k = a[i] + 1; // a[i] 表示1- n中第k小的数
        int l = 0, r = n;
        while(l < r)
        {
            int mid = l + r >> 1;
            if(fen.sum(mid) >= k)
                r = mid;
            else
                l = mid + 1;
        }
        res[i] = l;
        fen.add(l, -1);
    }

    for (int i = 1; i <= n; i++)
        std::cout << res[i] << '\n';

    return 0;
}

#include <bits/stdc++.h>

using i64 = long long;

template <typename T>
struct Fenwick
{
    const int n;
    std::vector<T> tr, tri;
    Fenwick(int n) : n(n), tr(n + 1), tri(n + 1) {}
    void add(int x, T c)
    {
        for (int i = x; i <= n; i += i & -i)
            tr[i] += c;
    }
    void addi(int x, T c)
    {
        for (int i = x; i <= n; i += i & -i)
            tri[i] += c;
    }
    T sum(int x)
    {
        T res = 0;
        for (int i = x; i; i -= i & -i)
            res += tr[i];
        return res;
    }
    T sumi(int x)
    {
        T res = 0;
        for (int i = x; i; i -= i & -i)
            res += tri[i];
        return res;
    }
    T sum_point(int x)
    {
        return (i64)(x + 1) * sum(x) - sumi(x);
    }
    T get_sum(int l, int r)
    {
        return sum_point(r) - sum_point(l - 1);
    }
};

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, m;
    std::cin >> n >> m;

    Fenwick<i64> fen(n);

    std::vector<i64> a(n + 1);
    for (int i = 1; i <= n; i++)
        std::cin >> a[i], fen.add(i, a[i] - a[i - 1]), fen.addi(i, (a[i] - a[i - 1]) * i);

    while (m--)
    {
        char op[2];
        std::cin >> op;
        if (op[0] == 'C')
        {
            int l, r, d;
            std::cin >> l >> r >> d;
            fen.add(l, d), fen.add(r + 1, -d);
            fen.addi(l, l * d), fen.addi(r + 1, (r + 1) * (-d));
        }
        else
        {
            int l, r;
            std::cin >> l >> r;

            // 暴力写法
            // for (int i = l; i <= r; i++)
            //     res += fen.sum(i);

            std::cout << fen.get_sum(l, r) << '\n';
        }
    }

    return 0;
}

#include <bits/stdc++.h>

using i64 = long long;

template <typename T>
struct Fenwick
{
    const int n;
    std::vector<T> tr;
    Fenwick(int n) : n(n), tr(n + 1) {}
    void clear()
    {
        std::fill(tr.begin(), tr.end(), 0);
    }
    void add(int x, int c)
    {
        for (int i = x; i <= n; i += i & -i)
            tr[i] += c;
    }
    T sum(int x)
    {
        T res = 0;
        for (int i = x; i; i -= i & -i)
            res += tr[i];
        return res;
    }
    T rangesum(int l, int r)
    {
        return sum(r) - sum(l);
    }
};

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, m;
    std::cin >> n >> m;

    Fenwick<int> fen(n);

    std::vector<int> a(n + 1), s(n + 1);
    for (int i = 1; i <= n; i++)
        std::cin >> a[i], s[i] = a[i] - a[i - 1], fen.add(i, s[i]);

    while(m--)
    {
        char op[2];
        std::cin >> op;
        if(op[0] == 'C')
        {
            int l, r, d;
            std::cin >> l >> r >> d;
            fen.add(l, d), fen.add(r + 1, -d);
        }
        else 
        {
            int x;
            std::cin >> x;
            std::cout << fen.sum(x) << '\n';
        }
    }

    return 0;
}

#include <bits/stdc++.h>

using i64 = long long;

struct BIT
{
    const int n;
    std::vector<int> tr;
    BIT(int n) : n(n), tr(n + 1) {}
    void clear()
    {
        std::fill(tr.begin(), tr.end(), 0);
    }
    void add(int x, int c)
    {
        for (int i = x; i <= n; i += i & -i)
            tr[i] += c;
    }
    i64 sum(int x)
    {
        i64 res = 0;
        for (int i = x; i; i -= i & -i)
            res += tr[i];
        return res;
    }
};

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    std::cin >> n;

    std::vector<int> a(n + 1);
    for (int i = 1; i <= n; i++)
        std::cin >> a[i];

    BIT bit(n);

    std::vector<int> greater(n + 1), lower(n + 1);
    for (int i = 1; i <= n; i++)
    {
        int t = a[i];
        lower[i] = bit.sum(t - 1);
        greater[i] = bit.sum(n) - bit.sum(t);
        bit.add(t, 1);
    }

    bit.clear();

    i64 res1 = 0, res2 = 0;
    for (int i = n; i >= 1; i--)
    {
        int t = a[i];
        res1 += (i64)lower[i] * bit.sum(t - 1);
        res2 += (i64)greater[i] * (bit.sum(n) - bit.sum(t));
        bit.add(t, 1);
    }
    std::cout << res2 << ' ' << res1 << '\n';

    return 0;
}

template <typename T>
struct Fenwick
{
    const int n;
    std::vector<T> a;
    Fenwick(int n) : n(n), a(n) {}
    void add(int x, T v)
    {
        for (int i = x + 1; i <= n; i += i & -i)
        {
            a[i - 1] += v;
        }
    }
    T sum(int x)
    {
        T ans = 0;
        for (int i = x; i > 0; i -= i & -i)
        {
            ans += a[i - 1];
        }
        return ans;
    }
    T rangeSum(int l, int r)
    {
        return sum(r) - sum(l);
    }
};

#include <bits/stdc++.h>

using i64 = long long;

constexpr double inf = 1e20;

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    std::cin >> n;

    std::pair<int, int> q[n];
    for (int i = 0; i < n; i++)
        std::cin >> q[i].first >> q[i].second;

    std::vector g(n, std::vector<char>(n));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            std::cin >> g[i][j];

    auto get_dis = [&](std::pair<int, int> a, std::pair<int, int> b)
    {
        double x = a.first - b.first, y = a.second - b.second;
        return sqrt(x * x + y * y);
    };

    std::vector dis(n, std::vector<double>(n));
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (g[i][j] == '0')
                dis[i][j] = inf;
            else
                dis[i][j] = get_dis(q[i], q[j]);
        }
    }
    for (int i = 0; i < n; i++)
        dis[i][i] = 0;
    for (int k = 0; k < n; k++)
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                dis[i][j] = std::min(dis[i][j], dis[i][k] + dis[k][j]);

    double res1 = 0;
    std::vector<double> maxn(n);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (dis[i][j] != inf)
            {
                maxn[i] = std::max(maxn[i], dis[i][j]);
                res1 = std::max(res1, maxn[i]);
            }

    double res2 = inf;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
        {
            if (dis[i][j] == inf)
                res2 = std::min(res2, maxn[i] + get_dis(q[i], q[j]) + maxn[j]);
        }

    auto findMax = [&](int x, int y)
    {
        double res = 0;
        for (int i = 1; i <= n; i++)
        {
            if (dis[i][x] <= inf / 2 || dis[i][y] <= inf / 2)
                res = std::max(res, maxn[i]);
        }
        return res;
    };

    std::cout << std::fixed << std::setprecision(6) << std::max(res1, res2) << '\n';
    return 0;
}

/*
    @@@
    @1@
    @@@
     |   @@@
     |   @4@
100  |   @@@
     |
     |
    @@@          @@@
    @2@----------@3@
    @@@   100    @@@
*/