Cod sursa(job #3306554)

Utilizator xDemonstyMatei Haba Ionut xDemonsty Data 12 august 2025 09:30:25
Problema Arbore Scor 0
Compilator cpp-64 Status done
Runda Lista lui wefgef Marime 2.68 kb
#include <fstream>
#include <vector>
#include <set>
using namespace std;
const int N=2e5+5,sqrt=300;
ifstream cin("arbore.in");
ofstream cout("arbore.out");
struct apar
{
    int suma;
    multiset<int>st;
    int in,fin;
    void init()
    {
        for(int i=in;i<fin;i++)
            st.insert(0);
    }
}block[N];
vector<int>adj[N];
int euler[N],unde[N],sub[N],q,n,global;
void citeste()
{
    cin>>n>>q;
    for(int i=1;i<n;i++)
    {
        int a,b;
        cin>>a>>b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
}
void dfs(int nod,int p)
{
    global++;
    euler[global]=nod;
    unde[nod]=global;
    sub[nod]=1;
    for(auto u:adj[nod])
    {
        if(u!=nod)
        {
            dfs(u,nod);
            sub[nod]+=sub[u];
        }
    }
}
int ce[sqrt+1];
int valori[N];
void update(int l,int r ,int suma)
{
    if(l>r)
        return;
    int parte=ce[l];
    if(l==block[parte].in&&block[parte].fin<=r)
    {
        block[parte].suma+=suma;
    }
    else
    {
        for(int i=l;i<=min(r,block[parte].fin);i++)
        {
            block[parte].st.erase(block[parte].st.find(valori[i]));
            valori[i]+=suma;
            block[parte].st.insert(valori[i]);
        }
        update(block[parte].fin+1,r,suma);
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    citeste();
    dfs(1,0);
    for(int i=1;i<=n;i++)
    {
        int blk=(i-1)/sqrt;
        ce[i]=blk;
        if(i/sqrt!=(i-1)/sqrt)
            block[blk].fin=i;
        if(i==1||(i-2)/sqrt!=(i-1)/sqrt)
            block[blk].in=i;
    }

    for(int i=1;i<=q;i++)
    {
        int tip;
        cin>>tip;
        if(tip==1)
        {
            int nod,suma;
            cin>>nod>>suma;
            int l=unde[nod];
            int r=unde[nod]+sub[nod]-1;
            update(l,r,suma);
        }
        else
        {
            int val;
            cin>>val;
            bool da=false;
            for(int i=0;i<=(n-1)/sqrt;i++)
            {
                int offset=block[i].suma;
                if(block[i].st.find(val-offset)!=block[i].st.end())
                {
                    da=true;
                    for(int j=block[i].in;j<=block[i].fin;j++)
                    {
                        if(valori[j]==(val-offset))
                        {
                            cout<<euler[j]<<'\n';
                            break;
                        }
                    }
                }
                if(da)
                    break;
            }
            if(!da)
                cout<<-1<<'\n';
        }

    }


    return 0;
}