oj.uz

답안 #809228

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
809228 2023-08-05T22:27:53 Z ashcomp Sumtree (INOI20_sumtree) C++14
10 / 100
 538 ms 203964 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]);
        }
}//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.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 192 ms 199744 KB Output is correct
2 Correct 174 ms 199648 KB Output is correct
3 Correct 188 ms 199628 KB Output is correct
4 Correct 174 ms 199644 KB Output is correct
5 Correct 169 ms 193884 KB Output is correct
6 Correct 62 ms 149936 KB Output is correct
7 Correct 62 ms 149712 KB Output is correct
8 Correct 66 ms 149752 KB Output is correct
9 Correct 173 ms 190456 KB Output is correct
10 Correct 171 ms 190164 KB Output is correct
11 Correct 176 ms 190412 KB Output is correct
12 Correct 160 ms 188500 KB Output is correct
13 Correct 156 ms 195884 KB Output is correct

Subtask #2
0 / 20.0

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

Subtask #3
0 / 20.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 192 ms 199744 KB Output is correct
2 Correct 174 ms 199648 KB Output is correct
3 Correct 188 ms 199628 KB Output is correct
4 Correct 174 ms 199644 KB Output is correct
5 Correct 169 ms 193884 KB Output is correct
6 Correct 62 ms 149936 KB Output is correct
7 Correct 62 ms 149712 KB Output is correct
8 Correct 66 ms 149752 KB Output is correct
9 Correct 173 ms 190456 KB Output is correct
10 Correct 171 ms 190164 KB Output is correct
11 Correct 176 ms 190412 KB Output is correct
12 Correct 160 ms 188500 KB Output is correct
13 Correct 156 ms 195884 KB Output is correct
14 Incorrect 61 ms 149008 KB Output isn't correct
15 Halted 0 ms 0 KB -