제출 #809228

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
809228		ashcomp	Sumtree (INOI20_sumtree)	C++14	10 / 100	538 ms	203964 KiB

Main

#include<bits/stdc++.h>

using namespace std;
 
#define all(x) x.begin() , x.end()
#define pii pair<int, int>
#define piii pair<int, pii>
#define pll pair<ll, ll>
#define plll pair<ll, pll>
#define pb push_back
#define qb pop_back
#define F first
#define S second
#define wall cerr<<"--------------------------------------"<<endl
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-O2")
 
typedef long long ll;
typedef double db;

const ll INF = 1e9;
const ll maxn = 5e5 + 10;
const ll mod = 1e9 + 7;

ll n , q , k , sz[maxn] , st[maxn] , en[maxn] , h[maxn] , ti=1 , ans;
vector<ll> g[maxn] , ANS; 

ll fac[maxn] , inv[maxn];
ll pw(ll a , ll b)
{
        ll res = 1;
        while(b){
                if(b&1)res = (res*a)%mod;
                b>>=1; a=(a*a)%mod;
        }
        return res;
}
ll choose(ll a , ll b)
{
        if(b>a || b<0)return 0;

        ll A = fac[a];
        ll B = (inv[b] * inv[a-b])%mod;
        ll C = (A*B)%mod;
        return C;
}
void preps()
{
        fac[0] = 1;
        for(int i=1; i<maxn; i++){
                fac[i] = (fac[i-1] * i)%mod;
        }
        inv[maxn-1] = pw(fac[maxn-1],mod-2);
        for(ll i=maxn-1; i>0; i--){
                inv[i-1] = (inv[i]*i)%mod;
        }
        for(int i=1; i<maxn; i++){
                sz[i] = 1;
        }
}//ok

void dfs(ll v , ll p)
{
        st[v] = ti++;
        en[v] = st[v];
        for(auto u : g[v]){
                if(u==p)continue;
                h[u] = h[v] + 1;
                dfs(u,v);
                sz[v] += sz[u];
                en[v] = max(en[v],en[u]);
        }
}//ok

struct PAR_segment{
        set<pll> seg[maxn<<2];
        void build(ll tl=1 , ll tr=n , ll v=1)
        {
                seg[v].insert({INF,INF});
                if(tl==tr)return;
                ll mid=(tl+tr)>>1 , ml=(v<<1) , mr=(v<<1)|1;
                build(tl,mid,ml);
                build(mid+1,tr,mr);
        }
        void upd(pll val , ll l , ll r , ll tl=1 , ll tr=n , ll v=1)
        {
                if(l>r)return;
                if(l==tl && r==tr){
                        seg[v].insert(val);
                        return;
                }
                ll mid=(tl+tr)>>1 , ml=(v<<1) , mr=(v<<1)|1;
                upd(val,l,min(r,mid),tl,mid,ml);
                upd(val,max(l,mid+1),r,mid+1,tr,mr);
        }
        void del(pll val , ll l , ll r , ll tl=1 , ll tr=n , ll v=1)
        {
                if(l>r)return;
                if(l==tl && r==tr){
                        seg[v].erase(val);
                        return;
                }
                ll mid=(tl+tr)>>1 , ml=(v<<1) , mr=(v<<1)|1;
                del(val,l,min(r,mid),tl,mid,ml);
                del(val,max(l,mid+1),r,mid+1,tr,mr);
        }
        pll ask(ll pos , ll tl=1 , ll tr=n , ll v=1){
                if(tl==tr){
                        pll res = *seg[v].begin();
                        return res;
                }
                ll mid=(tl+tr)>>1 , ml=(v<<1) , mr=(v<<1)|1;
                pll res = *seg[v].begin() , e;
                if(pos<=mid)e = ask(pos,tl,mid,ml);
                else e = ask(pos,mid+1,tr,mr);
                if(e.F < res.F){
                        return e;
                }else{
                        return res;
                }
        }
};

struct SZ_segment{
        pll seg[maxn<<2];
        ll lazy[maxn<<2];
        void build(int tl=1 , int tr=n , int v=1)
        {
                lazy[v] = 0;
                seg[v] = {1 , tr-tl+1};
                if(tl==tr)return;
                int mid=(tl+tr)>>1 , ml=(v<<1) , mr=(v<<1)|1;
                build(tl,mid,ml);build(mid+1,tr,mr);
        }
        void shift(ll tl , ll tr , ll v)
        {
                ll ml=(v<<1) , mr=(v<<1)|1;
                seg[v] = {lazy[v]+seg[v].F , seg[v].S};
                if(tl!=tr){
                        lazy[ml] += lazy[v];
                        lazy[mr] += lazy[v];
                }
                lazy[v] = 0;
        }
        void upd(ll val , ll l , ll r , ll tl=1 , ll tr=n , ll v=1)
        {
                shift(tl,tr,v);
                if(l>r)return;
                if(l==tl && r==tr){
                        lazy[v] += val;
                        shift(tl,tr,v);
                        return;
                }
                ll mid=(tl+tr)>>1 , ml=(v<<1) , mr=(v<<1)|1;
                upd(val,l,min(r,mid),tl,mid,ml);
                upd(val,max(l,mid+1),r,mid+1,tr,mr);
                if(seg[ml].F < seg[mr].F){
                        seg[v] = seg[ml];
                        return;
                }
                if(seg[ml].F > seg[mr].F){
                        seg[v] = seg[mr];
                        return;
                }
                seg[v] = {seg[ml].F , seg[ml].S+seg[mr].S};
        }
        pll ask(ll l , ll r , ll tl=1 , ll tr=n , ll v=1)
        {
                shift(tl,tr,v);
                if(l>r)return {INF,-1};
                if(l==tl && r==tr){
                        return seg[v];
                }
                ll mid=(tl+tr)>>1 , ml=(v<<1) , mr=(v<<1)|1;
                pll e1 = ask(l,min(r,mid),tl,mid,ml);
                pll e2 = ask(max(l,mid+1),r,mid+1,tr,mr);
                if(e1.F < e2.F){
                        return e1;
                }
                if(e1.F > e2.F){
                        return e2;
                }
                return {e1.F , e1.S+e2.S};
        }
};//ok

PAR_segment Par;
SZ_segment Sz;
int cnt[maxn] , temp[maxn];

int main()
{
        ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
        preps();
        cin>>n>>k;
        for(int i=1; i<n; i++){
                int v,u; cin>>v>>u;
                g[v].push_back(u);
                g[u].push_back(v);
        }
        dfs(1,1);
        /**/
        ans = choose(k+sz[1]-1 , sz[1]-1);
        ANS.push_back(ans);
        Par.build();
        Par.upd({-h[1],1},1,n);
        Sz.build();
        cnt[1] = n;
        temp[1] = k;
        /**/
        cin>>q;
        for(int i=1; i<=q; i++){
                int tp; cin>>tp;
                if(tp==1){
                        ll v,X; cin>>v>>X;
                        pll e = Par.ask(st[v]);ll p = e.S;
                        e = Sz.ask(st[v],en[v]); ll siz=e.S;
                        if(p==-1||p==INF||siz<=0){
                                while(n>0){
                                        cout<<"NOOOOO"<<endl;
                                }
                        }
                        //cout<<p<<" , "<<siz<<"\n";
                        /**/
                        ll x = choose(temp[p]+cnt[p]-1 , cnt[p]-1);
                        ans = (ans * pw(x,mod-2))%mod;
                        cnt[p] -= siz;
                        cnt[v] += siz;
                        temp[p] -= X;
                        temp[v] += X;
                        x = choose(temp[p]+cnt[p]-1 , cnt[p]-1);
                        ans = (ans * x)%mod;
                        x = choose(temp[v]+cnt[v]-1 , cnt[v]-1);
                        ans = (ans * x)%mod;
                        ANS.push_back(ans);
                        /**/
                        Par.upd({-h[v],v},st[v],en[v]);
                        Sz.upd(1,st[v],en[v]);
                }else{
                        int v; cin>>v;
                        Par.del({-h[v],v},st[v],en[v]);
                        pll e = Par.ask(st[v]);ll p = e.S;
                        e = Sz.ask(st[v],en[v]); ll siz=e.S;
                        if(p==-1||p==INF||siz<=0){
                                while(n>0){
                                        cout<<"NOOOOO"<<endl;
                                }
                        }
                        /**/
                        ll x = choose(temp[p]+cnt[p]-1 , cnt[p]-1);
                        ll y = choose(temp[v]+cnt[v]-1 , cnt[v]-1);
                        y = (y*x);
                        ans = (ans * pw(y,mod-2))%mod;
                        cnt[p] += siz;
                        cnt[v] -= siz;
                        temp[p] += temp[v];
                        temp[v] = 0;
                        x = choose(temp[p]+cnt[p]-1 , cnt[p]-1);
                        ans = (ans * x)%mod;
                        ANS.push_back(ans);
                        /**/
                        Sz.upd(-1,st[v],en[v]);
                }
        }
        for(auto u : ANS){
                cout<<u<<"\n";
        }
        return 0;
}
/*
3 3
1 2
2 3
2
1 3 1
1 2 1

*/
/*

*/
/*
by
          _____                    _____                    _____                    _____                  
         /\    \                  /\    \                  /\    \                  /\    \                 
        /::\    \                /::\    \                /::\____\                /::\    \                
       /::::\    \              /::::\    \              /:::/    /                \:::\    \               
      /::::::\    \            /::::::\    \            /:::/    /                  \:::\    \              
     /:::/\:::\    \          /:::/\:::\    \          /:::/    /                    \:::\    \             
    /:::/__\:::\    \        /:::/__\:::\    \        /:::/____/                      \:::\    \            
   /::::\   \:::\    \       \:::\   \:::\    \      /::::\    \                      /::::\    \           
  /::::::\   \:::\    \    ___\:::\   \:::\    \    /::::::\    \   _____    ____    /::::::\    \          
 /:::/\:::\   \:::\    \  /\   \:::\   \:::\    \  /:::/\:::\    \ /\    \  /\   \  /:::/\:::\    \         
/:::/  \:::\   \:::\____\/::\   \:::\   \:::\____\/:::/  \:::\    /::\____\/::\   \/:::/  \:::\____\        
\::/    \:::\  /:::/    /\:::\   \:::\   \::/    /\::/    \:::\  /:::/    /\:::\  /:::/    \::/    /        
 \/____/ \:::\/:::/    /  \:::\   \:::\   \/____/  \/____/ \:::\/:::/    /  \:::\/:::/    / \/____/         
          \::::::/    /    \:::\   \:::\    \               \::::::/    /    \::::::/    /                  
           \::::/    /      \:::\   \:::\____\               \::::/    /      \::::/____/                   
           /:::/    /        \:::\  /:::/    /               /:::/    /        \:::\    \                   
          /:::/    /          \:::\/:::/    /               /:::/    /          \:::\    \                  
         /:::/    /            \::::::/    /               /:::/    /            \:::\    \                 
        /:::/    /              \::::/    /               /:::/    /              \:::\____\                
        \::/    /                \::/    /                \::/    /                \::/    /                
         \/____/                  \/____/                  \/____/                  \/____/                 
                                                                                                            
*/
//NOGHRE SHODANAM BAD NIST :_)

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