Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define int ll
- typedef long long ll;
- using namespace std;
- vector<int> r;
- vector<int> ex;
- vector<int> par;
- vector<int> over;
- vector<int> adding;
- vector<vector<int>> sons;
- int getPar(int x) {
- if (par[x] == x) {
- return x;
- }
- return getPar(par[x]);
- }
- void join(int x, int y) {
- x = getPar(x);
- y = getPar(y);
- if (x == y) {
- return;
- }
- if (r[x] < r[y]) {
- swap(x, y);
- } else if (r[x] == r[y]) {
- r[x]++;
- }
- for (int i = 0; i < int(sons[y].size()); i++) {
- over[sons[y][i]] += adding[x];
- ex[sons[y][i]] += adding[y];
- sons[x].push_back(sons[y][i]);
- }
- par[y] = x;
- }
- void add(int x, int ex) {
- adding[getPar(x)] += ex;
- }
- int get(int x) {
- int parent = getPar(x);
- return ex[x] + adding[parent] - over[x];
- }
- signed main()
- {
- ios_base::sync_with_stdio(false);
- cin.tie(0);
- cout.tie(0);
- int n;
- cin >> n;
- r.resize(n + 1, 1);
- par.resize(n + 1);
- ex.resize(n + 1, 0);
- adding.resize(n + 1, 0);
- sons.resize(n + 1, vector<int>(0));
- for (int i = 0; i < n; i++) {
- par[i] = i;
- sons[i].push_back(i);
- }
- int m;
- cin >> m;
- string x;
- for (int i = 0; i < m; i++) {
- cin >> x;
- if (x == "add") {
- int a, b;
- cin >> a >> b;
- add(a - 1, b);
- } else if (x == "join") {
- int a, b;
- cin >> a >> b;
- join(a - 1, b - 1);
- } else {
- int a;
- cin >> a;
- cout << get(--a) << '\n';
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement