Cod sursa(job #3190808)

Utilizator YosifIosif Andrei Stefan Yosif Data 8 ianuarie 2024 09:14:22
Problema Arbore Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.45 kb
#include <bits/stdc++.h>
using namespace std;

string file = "arbore";
ifstream fin(file + ".in");
ofstream fout(file + ".out");

int n, m;
vector <int> g[100001];
int v[300001], sz, first[100001], last[100001];
unordered_map <long long, int> M[600];
long long add[600];
const int root = 550;

void dfs(int node = 1, int p = -1) {

    first[node] = last[node] = ++sz;

        for (auto &i : g[node])
            if (i != p) {

                dfs(i, node);
                last[node] = ++sz;
            }
}

int main() {

    fin >> n >> m;

    for (int i = 1; i < n; i++) {

        int x, y;
        fin >> x >> y;

        g[x].push_back(y);
        g[y].push_back(x);
    }

    dfs();

    for (int i = 1; i <= sz; i++)
        M[i / root][0]++;

    for (int i = 1; i <= m; i++) {

        int type;
        fin >> type;

        if (type == 1) {

            int p, s;
            fin >> p >> s;

            if (last[p] - first[p] + 1 <= 2 * root) {

                for (int j = first[p]; j <= last[p]; j++) {

                    M[j / root][v[j]]--;
                    v[j] += s;
                    M[j / root][v[j]]++;
                }
            }
            else {

                int x, y;
                x = first[p];
                y = last[p];

                int aux = (first[p] / root + 1) * root;

                for (int j = first[p]; j < aux; j++) {

                    M[j / root][v[j]]--;
                    v[j] += s;
                    M[j / root][v[j]]++;
                }

                x = aux;
                y -= y % root - 1;

                for (int j = last[p]; j > y; j--) {

                    M[j / root][v[j]]--;
                    v[j] += s;
                    M[j / root][v[j]]++;
                }

                for (int j = x; j <= y; j += root)
                    add[j / root] += s;
            }
        }
        else {

            int s;
            fin >> s;

            int aux = 0;

            for (int j = 1; j <= sz; j = (j / root + 1) * root) {

                if (M[j / root][s - add[j / root]]) {

                    aux = j;
                    break;
                }
            }

            if (aux == 0) {

                fout << "-1\n";
                continue;
            }

            for (int j = aux; j < (aux / root + 1) * root; j++)
                if (v[j] + add[j / root] == s) {

                    fout << j << '\n';
                    break;
                }
        }
    }

    return 0;
}