Cod sursa(job #3306567)

Utilizator xDemonstyMatei Haba Ionut xDemonsty Data 12 august 2025 10:04:34
Problema Arbore Scor 0
Compilator cpp-64 Status done
Runda Lista lui wefgef Marime 2.15 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!=p)
        {
            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;
        update(block[parte].fin+1,r,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;
    }
    block[ce[n]].fin=n;
    for(int i=0; i<=ce[n]; i++)
        block[i].init();

    //return 0;
    //cout<<block[0].fin<<" "<<"huh"<<'\n';
    for(int i=1; i<=q; i++)
    {
       int tip;
       cin>>tip;
       if(tip==1)
       {
           int a,b;
           cin>>a>>b;
       }
       else
       {
           int val;
           cin>>val;
           cout<<n;
           if(i!=q)
            cout<<'\n';
       }
    }


    return 0;
}