답안 #809217

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
809217 2023-08-05T22:16:26 Z ashcomp Sumtree (INOI20_sumtree) C++14
10 / 100
588 ms 196784 KB
#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]);
        }
}

struct PAR_segment{
        set<pii> seg[maxn<<2];
        void build(int tl=1 , int tr=n , int 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)
        {
                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};
        }
};

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;
                        /**/
                        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;
                        /**/
                        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<<" ";
        return 0;
}
/*
3 3
1 2
2 3
2
1 2 1
1 3 1
*/
/*

*/
/*
by
          _____                    _____                    _____                    _____                  
         /\    \                  /\    \                  /\    \                  /\    \                 
        /::\    \                /::\    \                /::\____\                /::\    \                
       /::::\    \              /::::\    \              /:::/    /                \:::\    \               
      /::::::\    \            /::::::\    \            /:::/    /                  \:::\    \              
     /:::/\:::\    \          /:::/\:::\    \          /:::/    /                    \:::\    \             
    /:::/__\:::\    \        /:::/__\:::\    \        /:::/____/                      \:::\    \            
   /::::\   \:::\    \       \:::\   \:::\    \      /::::\    \                      /::::\    \           
  /::::::\   \:::\    \    ___\:::\   \:::\    \    /::::::\    \   _____    ____    /::::::\    \          
 /:::/\:::\   \:::\    \  /\   \:::\   \:::\    \  /:::/\:::\    \ /\    \  /\   \  /:::/\:::\    \         
/:::/  \:::\   \:::\____\/::\   \:::\   \:::\____\/:::/  \:::\    /::\____\/::\   \/:::/  \:::\____\        
\::/    \:::\  /:::/    /\:::\   \:::\   \::/    /\::/    \:::\  /:::/    /\:::\  /:::/    \::/    /        
 \/____/ \:::\/:::/    /  \:::\   \:::\   \/____/  \/____/ \:::\/:::/    /  \:::\/:::/    / \/____/         
          \::::::/    /    \:::\   \:::\    \               \::::::/    /    \::::::/    /                  
           \::::/    /      \:::\   \:::\____\               \::::/    /      \::::/____/                   
           /:::/    /        \:::\  /:::/    /               /:::/    /        \:::\    \                   
          /:::/    /          \:::\/:::/    /               /:::/    /          \:::\    \                  
         /:::/    /            \::::::/    /               /:::/    /            \:::\    \                 
        /:::/    /              \::::/    /               /:::/    /              \:::\____\                
        \::/    /                \::/    /                \::/    /                \::/    /                
         \/____/                  \/____/                  \/____/                  \/____/                 
                                                                                                            
*/
//NOGHRE SHODANAM BAD NIST :_)
# 결과 실행 시간 메모리 Grader output
1 Correct 177 ms 189200 KB Output is correct
2 Correct 167 ms 189192 KB Output is correct
3 Correct 170 ms 189260 KB Output is correct
4 Correct 185 ms 189300 KB Output is correct
5 Correct 162 ms 183500 KB Output is correct
6 Correct 67 ms 149808 KB Output is correct
7 Correct 65 ms 149552 KB Output is correct
8 Correct 67 ms 149564 KB Output is correct
9 Correct 168 ms 180024 KB Output is correct
10 Correct 170 ms 179816 KB Output is correct
11 Correct 174 ms 180064 KB Output is correct
12 Correct 158 ms 178492 KB Output is correct
13 Correct 188 ms 186088 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Incorrect 68 ms 148988 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 221 ms 196784 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 588 ms 187948 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 177 ms 189200 KB Output is correct
2 Correct 167 ms 189192 KB Output is correct
3 Correct 170 ms 189260 KB Output is correct
4 Correct 185 ms 189300 KB Output is correct
5 Correct 162 ms 183500 KB Output is correct
6 Correct 67 ms 149808 KB Output is correct
7 Correct 65 ms 149552 KB Output is correct
8 Correct 67 ms 149564 KB Output is correct
9 Correct 168 ms 180024 KB Output is correct
10 Correct 170 ms 179816 KB Output is correct
11 Correct 174 ms 180064 KB Output is correct
12 Correct 158 ms 178492 KB Output is correct
13 Correct 188 ms 186088 KB Output is correct
14 Incorrect 68 ms 148988 KB Output isn't correct
15 Halted 0 ms 0 KB -