Submission #635525

#	Time	Username	Problem	Language	Result	Execution time	Memory
635525		Mahdi	Sumtree (INOI20_sumtree)	C++17	10 / 100	553 ms	28864 KiB

Main

#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
#define all(v) v.begin(), v.end()
#define F first
#define S second
typedef long long ll;
typedef pair<int, int> pii;
const int N=2e5+5, NN=3e5+5, M=1e9+7;
int ans, q, n, r, st[N], ts[N], fn[N], siz[N], num[N], ss[N], pr[N][18];
int f[N+NN], rf[N+NN], cmo;
vector<int>g[N];

int tav(int a, int b){
    int res=1;
    while(b){
        if(b&1)
            res=1LL*res*a%M;
        a=1LL*a*a%M;
        b>>=1;
    }
    return res;
}

int C(int x, int y){
    ll res=1LL*f[x]*rf[y]%M;
    res=res*rf[x-y]%M;
    return res;
}

void pre(){
    f[0]=1;
    for(int i=1;i<N+NN;++i)
        f[i]=1LL*f[i-1]*i%M;
    rf[N+NN-1]=tav(f[N+NN-1], M-2);
    for(int i=N+NN-2;i>=0;--i)
        rf[i]=1LL*(i+1)*rf[i+1]%M;
}

int ppp(int u, int t){
    for(int i=0;t>0;++i){
        if(t&1)
            u=pr[u][i];
        t>>=1;
    }
    return u;
}

struct seg_tree{
    int sz, h[3*N], lz[3*N], a[3*N], b[3*N];
    vector<int>ve;
    vector<pii>ev;

    seg_tree(){
        sz=1;
        while(sz<n)
            sz<<=1;
        memset(a, 0, sizeof(a));
        memset(b, 0, sizeof(b));
        memset(lz, 0, sizeof(lz));
        fill(h, h+2*sz, 1);
    }

    int suma(int x, int lx, int rx, int l, int r){
        if(lx>=r || rx<=l)
            return 0;
        if(lx>=l && rx<=r)
            return a[x];
        int m=(lx+rx)/2;
        return suma(2*x+1, lx, m, l, r)+suma(2*x+2, m, rx, l, r);
    }

    void adda(int x, int v){
        x=st[x];
        x+=sz-1;
        a[x]+=v;
        while(x){
            --x;
            x/=2;
            a[x]+=v;
        }
    }

    int sumb(int x, int lx, int rx, int l, int r){
        if(lx>=r || rx<=l)
            return 0;
        if(lx>=l && rx<=r)
            return b[x];
        int m=(lx+rx)/2;
        return sumb(2*x+1, lx, m, l, r)+sumb(2*x+2, m, rx, l, r);
    }

    void addb(int x, int v){
        x=st[x];
        x+=sz-1;
        b[x]+=v;
        while(x){
            --x;
            x/=2;
            b[x]+=v;
        }
    }

    void add(int x, int lx, int rx, int l, int r, int t){
        if(lx>=r || rx<=l)
            return;
        if(lx>=l && rx<=r){
            h[x]+=t;
            lz[x]+=t;
            return;
        }
        int m=(lx+rx)/2;
        h[2*x+1]+=lz[x];
        lz[2*x+1]+=lz[x];
        h[2*x+2]+=lz[x];
        lz[2*x+2]+=lz[x];
        lz[x]=0;
        add(2*x+1, lx, m, l, r, t);
        add(2*x+2, m, rx, l, r, t);
        h[x]=-max(-h[2*x+1], -h[2*x+2]);
    }

    void add(int l, int r, int t){
        add(0, 0, sz, l, r, t);
    }
    
    int min(int x, int lx, int rx, int i){
        if(lx==rx-1)
            return h[x];
        int m=(lx+rx)/2;
        h[2*x+1]+=lz[x];
        lz[2*x+1]+=lz[x];
        h[2*x+2]+=lz[x];
        lz[2*x+2]+=lz[x];
        lz[x]=0;
        if(i<m)
            return min(2*x+1, lx, m, i);
        return min(2*x+2, m, rx, i);    
    }

    void opr(int x, int lx, int rx, int r){
        if(lx>=r)
            return;
        if(rx<=r){
            ve.push_back(x);
            ev.push_back({lx, rx});
            return;
        }
        int m=(lx+rx)/2;
        h[2*x+1]+=lz[x];
        lz[2*x+1]+=lz[x];
        h[2*x+2]+=lz[x];
        lz[2*x+2]+=lz[x];
        lz[x]=0;
        opr(2*x+2, m, rx, r);
        opr(2*x+1, lx, m, r);
    }

    int fr(int x, int lx, int rx, int val){
        if(lx+1==rx){
            if(h[x]>=val)
                return lx;
            return rx;
        }
        int m=(lx+rx)/2;
        h[2*x+1]+=lz[x];
        lz[2*x+1]+=lz[x];
        h[2*x+2]+=lz[x];
        lz[2*x+2]+=lz[x];
        lz[x]=0;
        if(h[2*x+2]>=val)
            return fr(2*x+1, lx, m, val);
        return fr(2*x+2, m, rx, val);
    }

    int par(int u){
        int uu=st[u];
        int hh=min(0, 0, sz, uu);
        int l=0, r=n;
        while(l+1<r){
            int m=(l+r)/2;
            int w=ppp(u, m);
            if(min(0, 0, sz, st[w])==hh)
                l=m;
            else
                r=m;
        }
        return ppp(u, l);
        /*cout<<"---------------------------------\n";
        cout<<u<<' ';
        u=st[u];
        cout<<u<<'\n';
        opr(0, 0, sz, u+1);
        for(int i=0;i<ve.size();++i)
            cout<<"tof : "<<ve[i]<<' '<<ev[i].F<<", "<<ev[i].S<<'\n';
        int hh=min(0, 0, sz, u);
        cout<<hh<<'\n';
        int res=0;
        for(int i=0;i<ve.size();++i){
            if(h[ve[i]]<hh){
                cout<<"fuck : "<<ve[i]<<'\n';
                res=fr(ve[i], ev[i].F, ev[i].S, hh);
                break;
            }
        }
        cout<<res<<" "<<"aha\n";
        ve.clear();
        ev.clear();
        return ts[res];*/
    }
};

void dfs(int &tm, const int &v, const int &p=-1){
    ts[tm]=v;
    st[v]=tm++;
    ss[v]=1;
    for(int u: g[v]){
        if(u!=p){
            pr[u][0]=v;
            for(int i=1;i<18;++i)
                pr[u][i]=pr[pr[u][i-1]][i-1];
            dfs(tm, u, v);
            ss[v]+=ss[u];
        }
    }
    fn[v]=tm;
}

void ud(const int &v){
    if(num[v]<0)
        --cmo;
    else{
        ans=1LL*ans*tav(C(num[v]+siz[v]-1, siz[v]-1), M-2)%M;
       // cout<<"kok : "<<v<<" : "<<C(num[v]+siz[v]-1, siz[v]-1)<<'\n';
    }
}

void du(const int &v){
    if(num[v]<0)
        ++cmo;
    else{
       // cout<<"kko : "<<v<<", "<<num[v]<<", "<<siz[v]<<" "<<" : "<<C(num[v]+siz[v]-1, siz[v]-1)<<'\n';
        ans=1LL*ans*C(num[v]+siz[v]-1, siz[v]-1)%M;
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    pre();
    cin>>n>>r;
    for(int i=0;i<n-1;++i){
        int u, v;
        cin>>u>>v;
        g[--u].push_back(--v);
    }
    int tm=0;
    dfs(tm, 0);
    seg_tree A;
    ans=C(r+n-1, n-1);
    cout<<ans<<'\n';
    siz[0]=n;
    num[0]=r;
    cin>>q;
    while(q--){
        int t, u;
        cin>>t>>u;
        --u;
        if(t==1){
            int v;
            cin>>v;
            int w=A.par(u);
            //cout<<"par = "<<w<<'\n';
            A.add(st[u], fn[u], 1);
            ud(w);
            siz[u]=ss[u]-A.suma(0, 0, A.sz, st[u], fn[u]);
            A.adda(u, siz[u]);
            siz[w]-=siz[u];
            A.adda(w, -siz[u]);
            num[u]=v-A.sumb(0, 0, A.sz, st[u], fn[u]);
            A.addb(u, num[u]);
            num[w]-=num[u];
            A.addb(w, -num[u]);
            du(w);
            du(u);
        }
        else{
            A.add(st[u], fn[u], -1);
            int w=A.par(u);
           // cout<<"par = "<<u<<", "<<w<<'\n';
            ud(w);
            ud(u);
            A.adda(u, -siz[u]);
            siz[w]+=siz[u];
            A.adda(w, siz[u]);
            A.addb(u, -num[u]);
            num[w]+=num[u];
            A.addb(w, num[u]);
            siz[u]=num[u]=0;
            du(w);
        }
        if(cmo==0)
            cout<<ans<<'\n';
        else
            cout<<0<<'\n';
        //cout<<"fuck : "<<cmo<<", "<<ans<<'\n';
        /*for(int i=0;i<n;++i)
            cout<<siz[i]<<' ';
        cout<<'\n';
        for(int i=0;i<n;++i)
            cout<<num[i]<<' ';
        cout<<'\n';*/
    }
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 30