Submission #468569

#	Time	Username	Problem	Language	Result	Execution time	Memory
468569		alirezasamimi100	Sumtree (INOI20_sumtree)	C++17	100 / 100	2935 ms	61136 KiB

Main

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
/*#pragma comment(linker, "/stack:200000000")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma,tune=native")*/
/*#pragma GCC optimize("O2")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2,fma")*/
using namespace std;
using ll=long long int;
using ld=long double;
using pll=pair<ll,ll>;
using pii=pair<int,int>;
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define lc v<<1
#define rc v<<1|1
#define fast_io ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
const int N=2e5+10,LN=18,M=5e5+10,SQ=350,B=737,inf=1e9+10;
const ll INF=1e18;
const ld ep=1e-7;
const int MH=1000696969,MD=998244353,MOD=1000000007;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<pll, null_type,less<pll>, rb_tree_tag,tree_order_statistics_node_update>
ll pow(ll x, ll y, ll mod){
    ll ans=1;
    while (y != 0) {
        if (y & 1) ans = ans * x % mod;
        y >>= 1;
        x = x * x % mod;
    }
    return ans;
}
int n,g[N*4],st[N],fn[N],t,p[N][LN],lz[N*4],R,q,z;
ll F[M],I[M],ans;
pii f[N*4];
vector<int> adj[N];
pii operator+(pii a, pii b){
    if(a.F<b.F) return a;
    if(b.F<a.F) return b;
    return mp(a.F,a.S+b.S);
}
void dfs(int v, int P){
    p[v][0]=P;
    for(int i=1; i<LN; i++) p[v][i]=p[p[v][i-1]][i-1];
    st[v]=++t;
    for(int u : adj[v]) if(u!=P) dfs(u,v);
    fn[v]=t;
}
void update(int v, int l, int r, int p, int x){
    if(r-l==1){
        g[v]+=x;
        return;
    }
    int m=(l+r)>>1;
    if(p<m) update(lc,l,m,p,x);
    else update(rc,m,r,p,x);
    g[v]=g[lc]+g[rc];
}
int get(int v, int l, int r, int tl, int tr){
    if(l>=tr || tl>=r) return 0;
    if(l>=tl && r<=tr) return g[v];
    int m=(l+r)>>1;
    return get(lc,l,m,tl,tr)+get(rc,m,r,tl,tr);
}
void build(int v, int l, int r){
    f[v].S=r-l;
    if(r-l>1){
        ll m=(l+r)>>1;
        build(lc,l,m);
        build(rc,m,r);
    }
}
void shift(int v, int l, int r){
    f[v].F+=lz[v];
    if(r-l>1){
        lz[lc]+=lz[v];
        lz[rc]+=lz[v];
    }
    lz[v]=0;
}
void upd(int v, int l, int r, int tl, int tr, int x){
    shift(v,l,r);
    if(l>=tr || tl>=r) return;
    if(l>=tl && r<=tr){
        lz[v]+=x;
        return shift(v,l,r);
    }
    int m=(l+r)>>1;
    upd(lc,l,m,tl,tr,x);
    upd(rc,m,r,tl,tr,x);
    f[v]=f[lc]+f[rc];
}
pii gt(int v, int l, int r, int tl, int tr){
    shift(v,l,r);
    if(l>=tr || tl>=r) return mp(inf,0);
    if(l>=tl && r<=tr) return f[v];
    int m=(l+r)>>1;
    return gt(lc,l,m,tl,tr)+gt(rc,m,r,tl,tr);
}
ll C(int x, int y){
    if(y>x) return 0;
    return F[x]*I[y]%MOD*I[x-y]%MOD;
}
int fp(int v){
    int x=gt(1,1,n+1,st[v],st[v]+1).F;
    for(ll i=LN; i--;){
        int k=p[v][i];
        if(k && gt(1,1,n+1,st[k],st[k]+1).F==x) v=k;
    }
    return v;
}
ll calc(int v){
    int x=get(1,1,n+1,st[v],st[v]+1),y=gt(1,1,n+1,st[v],fn[v]+1).S;
    return C(x+y-1,y-1);
}
int main(){
    fast_io;
    cin >> n >> R;
    F[0]=I[0]=1;
    for(int i=1; i<M; i++){
        F[i]=F[i-1]*i%MOD;
        I[i]=pow(F[i],MOD-2,MOD);
    }
    for(int i=1; i<n; i++){
        ll v,u;
        cin >> v >> u;
        adj[v].pb(u);
        adj[u].pb(v);
    }
    dfs(1,0);
    build(1,1,n+1);
    upd(1,1,n+1,1,n+1,1);
    update(1,1,n+1,1,R);
    ans=calc(1);
    cout << ans << '\n';
    cin >> q;
    while(q--){
        int k,v,x,u,y;
        cin >> k >> v;
        if(k==1){
            cin >> x;
            u=fp(v);
            y=calc(u);
            if(y) ans=ans*pow(y,MOD-2,MOD)%MOD;
            else z--;
            x-=get(1,1,n+1,st[v],fn[v]+1);
            update(1,1,n+1,st[v],x);
            update(1,1,n+1,st[u],-x);
            upd(1,1,n+1,st[v],fn[v]+1,1);
            y=calc(u);
            if(y) ans=ans*y%MOD;
            else z++;
            y=calc(v);
            if(y) ans=ans*y%MOD;
            else z++;
        }else{
            u=fp(p[v][0]);
            y=calc(u);
            if(y) ans=ans*pow(y,MOD-2,MOD)%MOD;
            else z--;
            y=calc(v);
            if(y) ans=ans*pow(y,MOD-2,MOD)%MOD;
            else z--;
            upd(1,1,n+1,st[v],fn[v]+1,-1);
            x=get(1,1,n+1,st[v],st[v]+1);
            update(1,1,n+1,st[v],-x);
            update(1,1,n+1,st[u],x);
            y=calc(u);
            if(y) ans=ans*y%MOD;
            else z++;
        }
        if(z) cout << 0 << '\n';
        else cout << ans << '\n';
    }
    return 0;
}

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