Cod sursa(job #3305689)

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

using namespace std;

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

const int nmax = 1e5;
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]);
        }
    }
}

int mars[nmax + 2];

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

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

            int sum = 0, flagg = 0;
            for(int it = 1; it <= n; it++){
                sum += mars[it];
                if(sum == a){
                    out<<actually[it]<<"\n";
                    flagg = 1; break;
                }
            }

            if(!flagg){ out<<"-1\n"; }
        }
    }

    return 0;
}