oj.uz

답안 #635525

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
635525 2022-08-26T11:03:18 Z Mahdi Sumtree (INOI20_sumtree) C++17
10 / 100
 553 ms 28864 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, 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.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 69 ms 23116 KB Output is correct
2 Correct 66 ms 23024 KB Output is correct
3 Correct 77 ms 23096 KB Output is correct
4 Correct 80 ms 23084 KB Output is correct
5 Correct 93 ms 23372 KB Output is correct
6 Correct 16 ms 18380 KB Output is correct
7 Correct 15 ms 18516 KB Output is correct
8 Correct 15 ms 18388 KB Output is correct
9 Correct 67 ms 23536 KB Output is correct
10 Correct 68 ms 23612 KB Output is correct
11 Correct 72 ms 24272 KB Output is correct
12 Correct 93 ms 28864 KB Output is correct
13 Correct 67 ms 22676 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 13 ms 18260 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 93 ms 24652 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 553 ms 26252 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 69 ms 23116 KB Output is correct
2 Correct 66 ms 23024 KB Output is correct
3 Correct 77 ms 23096 KB Output is correct
4 Correct 80 ms 23084 KB Output is correct
5 Correct 93 ms 23372 KB Output is correct
6 Correct 16 ms 18380 KB Output is correct
7 Correct 15 ms 18516 KB Output is correct
8 Correct 15 ms 18388 KB Output is correct
9 Correct 67 ms 23536 KB Output is correct
10 Correct 68 ms 23612 KB Output is correct
11 Correct 72 ms 24272 KB Output is correct
12 Correct 93 ms 28864 KB Output is correct
13 Correct 67 ms 22676 KB Output is correct
14 Incorrect 13 ms 18260 KB Output isn't correct
15 Halted 0 ms 0 KB -