oj.uz

Submission #636138

# Submission time Handle Problem Language Result Execution time Memory
636138 2022-08-28T09:13:09 Z Mahdi Sumtree (INOI20_sumtree) C++17
10 / 100
 559 ms 53624 KB 
#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], dis[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){
            dis[u]=dis[v]+1;
            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){
        if(lx>=r || rx<=l)
            return 0;
        if(lx>=l && rx<=r)
            return b[x];
        int m=(lx+rx)/2;
        return suma(2*x+1, lx, m, l, r)+suma(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);
    }
} 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);
    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);
    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);
    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);
        if(cmo==0)
            cout<<ans<<'\n';
        else
            cout<<0<<'\n';
    }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 44380 KB Output is correct
2 Correct 168 ms 44348 KB Output is correct
3 Correct 147 ms 44332 KB Output is correct
4 Correct 153 ms 44376 KB Output is correct
5 Correct 131 ms 39572 KB Output is correct
6 Correct 12 ms 9596 KB Output is correct
7 Correct 10 ms 9304 KB Output is correct
8 Correct 10 ms 9392 KB Output is correct
9 Correct 155 ms 35208 KB Output is correct
10 Correct 160 ms 35028 KB Output is correct
11 Correct 153 ms 35196 KB Output is correct
12 Correct 140 ms 33940 KB Output is correct
13 Correct 130 ms 41696 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 8916 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 178 ms 53624 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 559 ms 47480 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 44380 KB Output is correct
2 Correct 168 ms 44348 KB Output is correct
3 Correct 147 ms 44332 KB Output is correct
4 Correct 153 ms 44376 KB Output is correct
5 Correct 131 ms 39572 KB Output is correct
6 Correct 12 ms 9596 KB Output is correct
7 Correct 10 ms 9304 KB Output is correct
8 Correct 10 ms 9392 KB Output is correct
9 Correct 155 ms 35208 KB Output is correct
10 Correct 160 ms 35028 KB Output is correct
11 Correct 153 ms 35196 KB Output is correct
12 Correct 140 ms 33940 KB Output is correct
13 Correct 130 ms 41696 KB Output is correct
14 Incorrect 11 ms 8916 KB Output isn't correct
15 Halted 0 ms 0 KB -