#pragma GCC target ("avx2") #pragma GCC optimize ("Ofast") #include #include #include #include namespace niu { struct fastin { static const int bufsize = 1 << 24; char buf[bufsize]; char* iter; fastin() { iter = buf; for(int t = 0, k; (k = read(STDIN_FILENO, buf + t, sizeof(buf)) - t) > 0; t += k); } fastin& operator>>(int& num) { num = 0; bool neg = false; while(*iter < '+') iter++; if(*iter == '-') { neg = true; iter++; } else if(*iter == '+') iter++; while(*iter >= '0') num = 10 * num + *(iter++) - '0'; if(neg) num = -num; return *this; } } fin; struct fastout { static const int bufsize = 1 << 24; char buf[bufsize]; char* iter; fastout() { iter = buf; } ~fastout() { for(int t = 0, k; (k = write(STDOUT_FILENO, buf + t, iter - buf - t)) > 0; t += k); } fastout& operator<<(int num) { static char tmp[20]; if(num == 0) { *(iter++) = '0'; return *this; } if(num < 0) { *(iter++) = '-'; num = -num; } int i = 0; while(num) { tmp[i++] = num % 10; num /= 10; } while(i--) { *(iter++) = tmp[i] + '0'; } return *this; } fastout& operator<<(char c) { *(iter++) = c; return *this; } } fout; } struct union_find { std::vector par; std::vector Sigma; union_find(int N): par(N, -1) , Sigma(N, 0) { } int root(int x) { if(par[x] < 0) { return x; } int v = x; while(par[par[v]] >= 0) { v = par[v]; Sigma[x] += Sigma[v]; } par[x] = par[v]; return par[v]; } std::tuple unite(int x, int y) { x = root(x); y = root(y); if(x == y) return { -1, -1 }; if(par[x] > par[y]) std::swap(x, y); par[x] += par[y]; par[y] = x; Sigma[y] -= Sigma[x]; return { x, y }; } void add(int v, int a) { Sigma[root(v)] += a; } int value(int v) { int r = root(v); if(r == v) { return Sigma[v]; } else { return Sigma[v] + Sigma[r]; } } }; #include using namespace std; using i64 = long long; #define rep(i,s,e) for(i64 (i) = (s);(i) < (e);(i)++) #define all(x) x.begin(),x.end() int main() { int N, Q; niu::fin >> N >> Q; union_find uf(N); while(Q--) { int t, a, b; niu::fin >> t >> a >> b; a--; if(t == 1) { b--; uf.unite(a, b); } else if(t == 2) { uf.add(a, b); } else { niu::fout << uf.value(a) << '\n'; } /* cout << Q << endl; rep(i,0,N) { cout << i << " = " << uf.Sigma[i] << " " << uf.par[i] << endl; }*/ } }