oj.uz

답안 #809214

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
809214 2023-08-05T22:09:56 Z ashcomp Sumtree (INOI20_sumtree) C++14
10 / 100
 515 ms 199220 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;
        }
}

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].S += lazy[v];
                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[mr].F < seg[ml].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.S){
                        return e1;
                }
                if(e1.F > e2.S){
                        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();
        //Sz.upd(1,1,n);
        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;
                        //cout<<e.F<<" , "<<e.S<<"\n";
                        /**/
                        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;
                        //cout<<cnt[p]<<" , "<<temp[p]<<"\n";
                        cnt[p] += siz;
                        cnt[v] -= siz;
                        temp[p] += temp[v];
                        temp[v] = 0;
                        //cout<<cnt[p]<<" , "<<temp[p]<<"\n";
                        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 2
1 2
2 3
2
1 2 1
2 2
*/
/*

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

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 167 ms 191692 KB Output is correct
2 Correct 188 ms 191736 KB Output is correct
3 Correct 177 ms 191692 KB Output is correct
4 Correct 169 ms 191688 KB Output is correct
5 Correct 165 ms 185976 KB Output is correct
6 Correct 72 ms 149872 KB Output is correct
7 Correct 68 ms 149456 KB Output is correct
8 Correct 68 ms 149584 KB Output is correct
9 Correct 167 ms 182524 KB Output is correct
10 Correct 172 ms 182264 KB Output is correct
11 Correct 187 ms 182492 KB Output is correct
12 Correct 156 ms 180768 KB Output is correct
13 Correct 156 ms 188368 KB Output is correct

Subtask #2
0 / 20.0

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

Subtask #3
0 / 20.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 167 ms 191692 KB Output is correct
2 Correct 188 ms 191736 KB Output is correct
3 Correct 177 ms 191692 KB Output is correct
4 Correct 169 ms 191688 KB Output is correct
5 Correct 165 ms 185976 KB Output is correct
6 Correct 72 ms 149872 KB Output is correct
7 Correct 68 ms 149456 KB Output is correct
8 Correct 68 ms 149584 KB Output is correct
9 Correct 167 ms 182524 KB Output is correct
10 Correct 172 ms 182264 KB Output is correct
11 Correct 187 ms 182492 KB Output is correct
12 Correct 156 ms 180768 KB Output is correct
13 Correct 156 ms 188368 KB Output is correct
14 Incorrect 67 ms 149164 KB Output isn't correct
15 Halted 0 ms 0 KB -