!!!声明：本人自用模板，谨慎使用，比赛中出现bug概不负责。

`BigInt`高精度整数（不含负数）

struct BigInt {
    std::vector<char> v;
    BigInt(int x = 0) : v{} {
        do v.push_back(x % 10); while (x /= 10);
    }
    BigInt(std::string &x) : v{} {
        assert(size(x) != 0);
        for (int i = (int)size(x) - 1; i >= 0; --i) {
            v.push_back(x[i] - '0');
        }
    }
    BigInt &operator=(int x) {
        v.clear();
        do v.push_back(x % 10); while (x /= 10);
        return *this;
    }
    BigInt &operator=(const BigInt &x) {
        v.resize(x.v.size());
        memcpy(const_cast<char *>(v.data()), x.v.data(), x.v.size() * sizeof(char));
        return *this;
    }
    friend bool operator==(const BigInt &a, const BigInt &b) {
        if (size(a.v) == size(b.v)) {
            int idx = 0;
            while (idx < (int)size(a.v) && a.v[idx] == b.v[idx]) idx++; 
            return idx < (int)size(a.v);
        } else {
            return false;
        }
    }
    friend bool operator!=(const BigInt &a, const BigInt &b) {
        return !(a == b);
    }
    friend bool operator<(const BigInt &a, const BigInt &b) {
        if (size(a.v) == size(b.v)) {
            int idx = size(a.v) - 1;
            while (idx >= 0 && a.v[idx] == b.v[idx]) idx--; 
            return idx >= 0 && a.v[idx] < b.v[idx];
        }
        return size(a.v) < size(b.v);
    }
    friend bool operator<=(const BigInt &a, const BigInt &b) {
        if (size(a.v) == size(b.v)) {
            int idx = size(a.v) - 1;
            while (idx >= 0 && a.v[idx] == b.v[idx]) idx--; 
            return idx == -1 || a.v[idx] <= b.v[idx];
        }
        return size(a.v) < size(b.v);
    }
    friend bool operator>(const BigInt &a, const BigInt &b) {
        if (size(a.v) == size(b.v)) {
            int idx = size(a.v) - 1;
            while (idx >= 0 && a.v[idx] == b.v[idx]) idx--; 
            return idx >= 0 && a.v[idx] > b.v[idx];
        }
        return size(a.v) > size(b.v);
    }
    friend bool operator>=(const BigInt &a, const BigInt &b) {
        if (size(a.v) == size(b.v)) {
            int idx = size(a.v);
            while (idx >= 0 && a.v[idx] == b.v[idx]) idx--;
            return idx == -1 || a.v[idx] >= b.v[idx];
        }
        return size(a.v) > size(b.v);
    }
    BigInt &operator+=(const BigInt &x) & {
        int n = std::max<int>(size(v), size(x.v)), tmp = 0;
        bool flag = false;
        for (int i = 0; i < n; ++i) {
            if (i >= (int)size(v)) v.push_back(0);
            if (i < (int)size(x.v)) v[i] += x.v[i];
            if (flag) v[i] += 1, flag = false;
            if (v[i] >= 10) v[i] %= 10, flag = true;
        }
        if (flag) v.push_back(1);
        return *this;
    }
    BigInt &operator-=(const BigInt &x) & {
        assert(*this >= x);
        bool flag = false;
        for (int i = 0; i < (int)size(v); ++i) {
            if (i < (int)size(x.v)) v[i] -= x.v[i];
            if (flag) v[i] -= 1, flag = false;
            if (v[i] < 0) v[i] += 10, flag = true;
        }
        while (size(v) > 1 && v.back() == 0) v.pop_back();
        return *this;
    }
    BigInt &operator*=(const int &x) & {
        int tmp = 0;
        for (int i = 0; i < size(v); ++i) {
            tmp += (int)x * v[i];
            v[i] = tmp % 10;
            tmp /= 10;
        }
        while (tmp) {
            v.push_back(tmp % 10);
            tmp /= 10;
        }
        return *this;
    }
    BigInt &operator*=(const BigInt &x) & {
        BigInt result;
        result.v.resize(size(v) + size(x.v));
        for (int i = 0; i < (int)size(v); ++i) {
            for (int j = 0; j < (int)size(x.v); ++j) {
                result.v[i + j] += v[i] * x.v[j];
                result.v[i + j + 1] += result.v[i + j] / 10;
                result.v[i + j] %= 10;   
            }
        }
        while (size(result.v) > 1 && result.v.back() == 0) result.v.pop_back();
        return *this = result;
    }
    BigInt &operator/=(const int &x) & {
        int r = 0;
        for (int i = size(v) - 1; i >= 0; --i) {
            r = r * 10 + v[i];
            v[i] = r / x;
            r %= x;
        }
        while (size(v) > 1 && v.back() == 0) v.pop_back();
        return *this;
    }
    int operator%=(const int &x) {
        int r = 0;
        for (int i = size(v) - 1; i >= 0; --i) {
            r = r * 10 + v[i];
            r %= x;
        }
        return r;
    }
    friend BigInt operator+(BigInt a, const BigInt &b) {
        return a += b;
    }
    friend BigInt operator-(BigInt a, const BigInt &b) {
        return a -= b;
    }
    friend BigInt operator*(BigInt a, const int &b) {
        return a *= b;
    }
    friend BigInt operator*(BigInt a, const BigInt &b) {
        return a *= b;
    }
    friend BigInt operator/(BigInt a, const int &b) {
        return a /= b;
    }
    friend int operator%(BigInt a, const int &b) {
        return a %= b;
    }
    friend std::istream &operator>>(std::istream &is, BigInt &a) {
        std::string str;
        is >> str;
        a = BigInt(str);
        return is;
    }
    friend std::ostream &operator<<(std::ostream &os, const BigInt &a) {
        for (int i = a.v.size() - 1; i >= 0; --i) os << (char)(a.v[i] + '0');
        return os;
    }
};

DSU并查集

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