Disjoint set union with path compression.

DSU.cpp

class DSU {
   private:
    vector<int> arr;
    vector<int> size;

   public:
    DSU(int n) {
        arr.resize(n);
        for (int i = 0; i < n; i++) arr[i] = i;
        size.resize(n, 1);
    }

    int root(int a) {
        while (arr[a] != a) {
            arr[a] = arr[arr[a]];
            a = arr[a];
        }
        return a;
    }

    bool find(int a, int b) {
        return root(a) == root(b);
    }

    void merge(int a, int b) {
        int root_a = root(a);
        int root_b = root(b);
        if (root_a < root_b)
            swap(root_a, root_b);
        arr[root_b] = root_a;
        size[root_a] += size[root_b];
    }
};

dsu.cpp

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

int root(vector<int> &arr, int a) {
    while (arr[a] != a) {
        arr[a] = arr[arr[a]];
        a = arr[a];
    }
    return a;
}

void merge(vector<int> &arr, int a, int b) {
    arr[root(arr, a)] = root(arr, b);
}

bool find(vector<int> &arr, int a, int b) {
    return root(arr, a) == root(arr, b);
}

auto init(int n) {
    vector<int> arr(n);
    for (int i = 0; i < n; i++) arr[i] = i;
    return arr;
}

int main() {
    
    auto arr = init(5);

    merge(arr, 0, 1);
    merge(arr, 4, 1);
    merge(arr, 0, 2);

    cout << find(arr, 2, 4) << '\n';
}

maximum_subtree.cpp

/*

https://codeforces.com/blog/entry/66972

You are given a tree of A nodes having A-1 edges. Each node is numbered from 1 to A 
where 1 is the root of the tree. You are given Q queries. In each query, you will be given 
a unique integer j. You are required to remove the j'th numbered edge from the tree. 
This operation will divide a tree into two different trees. For each query, once you perform 
the remove operation, you are asked to tell the maximum size among all the sizes of the trees 
present till that query. 

Note:
  Once an edge is removed, it will be considered removed for all the further queries.
  It is guaranteed that each edge will be pointing to exactly two different nodes of the tree.
  Edges are numbered from 1 to A-1. Please read the input format for more clarification.

*/

class DSU {
   private:
    vector<int> arr;
    vector<int> size;

   public:
    int max_size;
    DSU(int n) {
        arr.resize(n);
        for (int i = 0; i < n; i++) arr[i] = i;
        size.resize(n, 1);
        max_size = 1;
    }
    int root(int a) {
        while (arr[a] != a) {
            arr[a] = arr[arr[a]];
            a = arr[a];
        }
        return a;
    }
    bool find(int a, int b) {
        return root(a) == root(b);
    }
    void merge(int a, int b) {
        int root_a = root(a);
        int root_b = root(b);
        if (root_a < root_b)
            swap(root_a, root_b);
        arr[root_b] = root_a;
        size[root_a] += size[root_b];
        max_size = max(max_size, size[root_a]);
    }
};

vector<int> Solution::solve(int A, vector<int> &B, vector<int> &C, vector<int> &D) {
    vector<int> res(D.size());
    auto dsu = DSU(A);

    unordered_set<int> indexes;
    for (int i : D)
        indexes.insert(i - 1);
    for (int i = 0; i < B.size(); i++)
        if (indexes.count(i) == 0)
            dsu.merge(B[i] - 1, C[i] - 1);

    for (int i = D.size() - 1; i >= 0; i--) {
        res[i] = dsu.max_size;
        dsu.merge(B[D[i] - 1] - 1, C[D[i] - 1] - 1);
    }

    return res;
}