Cod sursa(job #3305702)

Utilizator Andrei-Dani-10Pisla Andrei Daniel Andrei-Dani-10 Data 4 august 2025 11:40:30
Problema Arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.92 kb
#include <fstream>
#include <vector>

#include <unordered_map>

using namespace std;

ifstream in("arbore.in");
ofstream out("arbore.out");

const int nmax = 1e5, valmax = 1e6, block = 325, nrblocks = nmax / block;
int n, nrq, value[nmax + 2], type, a, b;
int preorder[nmax + 2], leaffsub[nmax + 2];
int actually[nmax + 2];
vector <int> muchii[nmax + 2];

void dfs(int node, int father){

    preorder[node] = (++preorder[0]);
    actually[preorder[0]] = node;
    leaffsub[node] = preorder[0];

    for(auto nxt : muchii[node]){
        if(nxt != father){
            dfs(nxt, node);
            leaffsub[node] = max(leaffsub[node], leaffsub[nxt]);
        }
    }
}

struct batog{
    unordered_map <int, int> blocks[nrblocks + 2];
    int marsblocks[nrblocks + 2], numberblocks;
    int valuepreorder[nmax + 2];

    int getblock(int x){ return x / block; }
    int getleftt(int x){ return x * block; }
    int getrightt(int x){ return (x + 1) * block - 1; }

    void add(int pos, int value, int baseblk){
        for(int blk = baseblk; blk <= numberblocks; blk++){
            if(getleftt(blk) <= pos && pos <= getrightt(blk)){
                for(int it = max(1, getleftt(blk)); it <= pos; it++){
                    blocks[blk][valuepreorder[it]]--;
                    valuepreorder[it] += value;
                    blocks[blk][valuepreorder[it]]++;
                }
                return;
            }else{ marsblocks[blk] += value; }
        }
    }

    int query(int value){
        for(int blk = 0; blk <= numberblocks; blk++){
            if(blocks[blk].find(value - marsblocks[blk]) != blocks[blk].end() &&
               blocks[blk][value - marsblocks[blk]] != 0){

                int lf = max(1, getleftt(blk));
                int rg = min(n, getrightt(blk));
                value -= marsblocks[blk];

                for(int it = lf; it <= rg; it++){
                    if(valuepreorder[it] == value)
                        return actually[it];
                }
            }
        }
        return -1;
    }
} sqrtdecomp;

int main(){

    in>>n>>nrq;
    for(int i = 1; i <= n - 1; i++){
        in>>a>>b;
        muchii[a].push_back(b);
        muchii[b].push_back(a);
    }

    dfs(1, 0);

    sqrtdecomp.numberblocks = (n / block + !!(n % block)) - 1;
    for(int blk = 0; blk <= sqrtdecomp.numberblocks; blk++){
        int lf = max(1, sqrtdecomp.getleftt(blk));
        int rg = min(n, sqrtdecomp.getrightt(blk));
        sqrtdecomp.blocks[blk][0] = rg - lf + 1;
    }

    for(int i = 1; i <= nrq; i++){
        in>>type;
        if(type == 1){
            in>>a>>b;
            sqrtdecomp.add(preorder[a] - 1, -b, sqrtdecomp.getblock(preorder[a] - 1));
            sqrtdecomp.add(leaffsub[a], b, sqrtdecomp.getblock(preorder[a] - 1));
        }else{
            in>>a;
            out<<sqrtdecomp.query(a)<<"\n";
        }

    }

    return 0;
}