Cod sursa(job #3305693)

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

#include <map>

using namespace std;

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

const int nmax = 1e5, valmax = 1e6, block = 400, 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{
    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){
        for(int blk = 0; blk <= numberblocks; blk++){
            if(getleftt(blk) <= pos && pos <= getrightt(blk)){
                for(int it = max(1, getleftt(blk)); it <= pos; it++)
                    valuepreorder[it] += value;
                return;
            }else{ marsblocks[blk] += value; }
        }
    }

    int query(int value){
        for(int i = 1; i <= n; i++){
            if(valuepreorder[i] + marsblocks[getblock(i)] == value)
                return actually[i];
        };

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

                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;
    }

    void debug(){
        out<<"Debug: ";
        for(int i = 1; i <= n; i++){
            out<<valuepreorder[i] + marsblocks[getblock(i)]<<" ";
        }; out<<"\n";
    }
} 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);
    }

    for(int i = 1; i <= n; i++)
        sqrtdecomp.blocks[0][0] = 1;

    dfs(1, 0);

    sqrtdecomp.numberblocks = (n / block + !!(n % block));

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

            out<<sqrtdecomp.query(a)<<"\n";
        }

        ///sqrtdecomp.debug();
    }

    return 0;
}