Cod sursa(job #3306655)

Utilizator xDemonstyMatei Haba Ionut xDemonsty Data 12 august 2025 16:58:29
Problema Arbore Scor 50
Compilator cpp-64 Status done
Runda Lista lui wefgef Marime 2.71 kb
#include <fstream>
#include <vector>
#include <cassert>
#include <set>
using namespace std;
const int N=1e5+5,sqrt=100;
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!=p)
        {
            dfs(u,nod);
            sub[nod]+=sub[u];
        }
    }
}
int ce[N];
int valori[N];
void update(int l,int r,int suma)
{

    while(l<=r)
    {
        int parte=ce[l];
        if(l==block[parte].in&&block[parte].fin<=r)
        {
            block[parte].suma+=suma;
            l=block[parte].fin+1;
        }
        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]);
            }
            l=block[parte].fin+1;
        }
    }
}
int main()
{
    citeste();
    dfs(1,0);
    for(int i=1; i<=n; i++)
    {
        int blk=(i-1)/sqrt;
        ce[i]=blk;
        if(i/sqrt!=blk)
            block[blk].fin=i;
        if(i==1||(i-2)/sqrt!=blk)
            block[blk].in=i;
    }
    block[ce[n]].fin=n;
    for(int i=0; i<=ce[n]; i++)
        block[i].init();
    for(int ind=1; ind<=q; ind++)
    {
        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;
            int ans=-1;
            for(int i=0; i<=ce[n]; i++)
            {
                int offset=block[i].suma;
                if(block[i].st.find(val-offset)!=block[i].st.end())
                {
                    for(int j=block[i].in; j<=block[i].fin; j++)
                    {
                        if(valori[j]==(val-offset))
                        {
                            ans=euler[j];
                            break;
                        }
                    }
                    break;
                }
            }
            cout<<ans<<'\n';
        }

    }


    return 0;
}