Submission #636258

#	Time	Username	Problem	Language	Result	Execution time	Memory
636258		Mahdi	Sumtree (INOI20_sumtree)	C++17	100 / 100	718 ms	68120 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, M=1e9+7;
int n, r, q, f[5*N/2], rf[5*N/2], ans, cmo, siz[N];
int ss[N], pr[N][18], st[N], fn[N];
vector<int>g[N];
ll tp[N];

inline int tav(int x, int y){
    ll res=1;
    while(y){
        if(y&1)
            res=res*x%M;
        y>>=1;
        x=1LL*x*x%M;
    }
    return res;
}

inline int rev(const int &x){
    return tav(x, M-2); 
}

void pre(){
    f[0]=1;
    int t=5*N/2;
    for(int i=1;i<t;++i)
        f[i]=1LL*f[i-1]*i%M;
    rf[t-1]=rev(f[t-1]);
    for(int i=t-2;i>=0;--i)
        rf[i]=1LL*rf[i+1]*(i+1)%M;
}

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

void dfs(int &tm, const int &v, const int &p=-1){
    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 dfs(){
    int tm=0;
    dfs(tm, 0);
}

struct seg_tree{
    int sz, h[3*N];
    ll a[3*N], b[3*N];
    
    void add(int x, int lx, int rx, int l, int r, int val){
        if(lx>=r || rx<=l)
            return;
        if(lx>=l && rx<=r){
            h[x]+=val;
            return;
        }
        int m=(lx+rx)/2;
        add(2*x+1, lx, m, l, r, val);
        add(2*x+2, m, rx, l, r, val);
    }

    int num(int x){
        x+=sz-1;
        int res=h[x];
        while(x){
            --x;
            x/=2;
            res+=h[x];
        }
        return res;
    }

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

    ll 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 addb(int x, int val){
        x+=sz-1;
        b[x]+=val;
        while(x){
            --x;
            x/=2;
            b[x]+=val;
        }
    }

    ll sumb(int x, int lx, int rx, int l, int r){
        //cout<<"shit "<<" : "<<x<<", "<<lx<<", "<<rx<<", "<<l<<", "<<r<<" : "<<b[x]<<'\n';
        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 upd(){
        sz=1;
        while(sz<n)
            sz<<=1;
        add(0, 0, sz, 0, n, 1);
        adda(0, n);
        addb(0, r);
        //cout<<"wtf: ";
        sumb(0, 0, sz, 0, n);
        /*cout<<"come on : ";
        for(int i=0;i<2*sz;++i)
            cout<<b[i]<<' ';
        cout<<'\n';
        cout<<"------------------------------\n";*/
    }
} A;

int par(int v){
    int h=A.num(st[v]);
    for(int i=17;i>=0;--i){
        int u=pr[v][i];
        if(A.num(st[u])==h)
            v=u;
    }
    return v;
}

inline void du(const int &u){
    if(tp[u]<0)
        ++cmo;
    else
        ans=1LL*ans*C(siz[u]+tp[u]-1, siz[u]-1)%M;
}

inline void ud(const int &u){
    if(tp[u]<0)
        --cmo;
    else
        ans=1LL*ans*rev(C(siz[u]+tp[u]-1, siz[u]-1))%M;
}

void add_u(int u, int v){
    int w=par(u);
    //cout<<"fuck : "<<w<<'\n';
    A.add(0, 0, A.sz, st[u], fn[u], 1);
    ud(w);
    siz[u]=ss[u]-A.suma(0, 0, A.sz, st[u], fn[u]);
    tp[u]=v-A.sumb(0, 0, A.sz, st[u], fn[u]);
    du(u);
    A.adda(st[u], siz[u]);
    A.addb(st[u], tp[u]);
    siz[w]-=siz[u];
    tp[w]-=tp[u];
    du(w);
    A.adda(st[w], -siz[u]);
    A.addb(st[w], -tp[u]);
}

void erase_u(int u){
    A.add(0, 0, A.sz, st[u], fn[u], -1);
    int w=par(u);
    //cout<<"fuck :: "<<w<<'\n';
    ud(u);
    ud(w);
    siz[w]+=siz[u];
    tp[w]+=tp[u];
    du(w);
    A.adda(st[u], -siz[u]);
    A.addb(st[u], -tp[u]);
    A.adda(st[w], siz[u]);
    A.addb(st[w], tp[u]);
    siz[u]=tp[u]=0;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    pre();
    cin>>n>>r;
    for(int i=1;i<n;++i){
        int u, v;
        cin>>u>>v;
        g[--u].push_back(--v);
        g[v].push_back(u);
    }
    dfs();
    A.upd();
    siz[0]=n;
    tp[0]=r;
    ans=C(r+n-1, n-1);
    /*for(int i=0;i<n;++i)
        cout<<A.sumb(0, 0, A.sz, st[i], fn[i])<<' ';
    cout<<'\n';*/
    cout<<ans<<'\n';
    cin>>q;
    while(q--){
        int t, u;
        cin>>t>>u;
        --u;
        if(t==1){
            int v;
            cin>>v;
            add_u(u, v);
        }
        else
            erase_u(u);
        //cout<<"ans = ";
        if(cmo==0)
            cout<<ans<<'\n';
        else
            cout<<0<<'\n';
        /*for(int i=0;i<n;++i)
            cout<<siz[i]<<' ';
        cout<<'\n';
        for(int i=0;i<n;++i)
            cout<<tp[i]<<' ';
        cout<<'\n';
        for(int i=0;i<n;++i)
            cout<<A.sumb(0, 0, A.sz, st[i], fn[i])<<' ';
        cout<<'\n';*/
    }
}
/*
9 10
1 2
1 3
3 4
3 9
9 6
9 8
5 6
7 6
5
1 3 11
1 6 7
2 3
1 7 7
2 6
*/

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