【題解】Codeforces EDU Course-2 Lesson-7-1 C. Experience

#include <iostream>
#include <vector>
using namespace std;
 
int n, m, a[200005], p[200005], d[200005];
vector <int> v[200005];
 
int pa(int x){
    if (x == p[x]) return x;
    return p[x] = pa(p[x]);
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++){
        v[i].push_back(i);
        p[i] = i;
    }
    string s;
    for (int i = 0, x, y; i < m; i++){
        cin >> s;
        if (s == "join"){
            cin >> x >> y;
            x = pa(x);
            y = pa(y);
            if (x == y) continue;
            if (v[x].size() < v[y].size()) swap(x, y);
            p[y] = x;
            while (v[y].size()){
                a[v[y].back()] -= d[x]-d[y];
                v[x].push_back(v[y].back());
                v[y].pop_back();
            }
        }
        else if (s == "add"){
            cin >> x >> y;
            d[pa(x)] += y;
        }
        else{
            cin >> x;
            cout << a[x]+d[pa(x)] << "\n";
        }
    }
}