Cod sursa(job #3334741)

Utilizator stefan_ciureaStefan Ciurea stefan_ciurea Data 19 ianuarie 2026 15:57:11
Problema Arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.25 kb
#include <bits/stdc++.h>

using namespace std;

const int BUCKETS=320,Nmax=1e5+5;

int v[Nmax],vstart[Nmax],vend[Nmax],normm[Nmax],vlazy[BUCKETS];
bool viz[Nmax];
vector<int> tree[Nmax];
unordered_map<int,int> fr[BUCKETS];
int timer;

void dfs(int node) {
    vstart[node]=++timer;
    normm[timer]=node;
    viz[node]=1;
    for (auto x:tree[node]) {
        if (!viz[x]) dfs(x);
    }
    vend[node]=timer;
}

void add(int poz, int nrb, int sum) {
    fr[nrb][v[poz]]--;
    if (!fr[nrb][v[poz]]) fr[nrb].erase(v[poz]);
    v[poz]+=sum;
    fr[nrb][v[poz]]++;
}

int main() {
    ifstream fin("arbore.in");
    ofstream fout("arbore.out");
    int n,m;
    fin>>n>>m;
    for (int i=1; i<=n-1; ++i) {
        int x,y;
        fin>>x>>y;
        tree[x]. push_back(y);
        tree[y].push_back(x);
    }
    dfs(1);
    int b=sqrt(n);
    for (int i=1,nrb=0; i<=n; i+=b,++nrb) {
        int end=min(i+b,n+1);
        fr[nrb][0]=(end-i);
    }
    while (m--) {
        int type;
        fin>>type;
        if (type==1) {
            int p,s;
            fin>>p>>s;
            int st=vstart[p],dr=vend[p];
            int x=(st-1)/b,y=(dr-1)/b;
            if (x==y) {
                for (int j=st; j<=dr; ++j) {
                    add(j,x,s);
                }
            } else {
                int c=min((x+1)*b+1,n+1);
                for (int j=st; j<c; ++j) {
                    add(j,x,s);
                }
                for (int j=dr; j>=y*b+1; --j) {
                    add(j,y,s);
                }
                for (int k=x+1; k<y; ++k) {
                    vlazy[k]+=s;
                }
            }
        }
        else {
            int s;
            fin>>s;
            int nrb=(n+b-1)/b;
            int ans=-1;
            for (int k=0,i=1; k<nrb && ans==-1; ++k,i+=b) {
                if (fr[k]. count(s-vlazy[k])) {
                    for (int j=i; j<=min(i+b-1,n); ++j) {
                        if (v[j]+vlazy[k]==s) {
                            ans=normm[j];
                            break;
                        }
                    }
                }
            }
            fout<<ans<<'\n';
        }
    }
    fin.close();
    fout.close();
    return 0;
}