oj.uz

답안 #809239

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
809239 2023-08-05T23:26:48 Z ashcomp Sumtree (INOI20_sumtree) C++14
30 / 100
 3000 ms 259544 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 = 3e5 + 10;
const ll N = 1e6 + 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[N] , inv[N];
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(ll i=1; i<N; i++){
                fac[i] = (fac[i-1] * i)%mod;
        }
        inv[N-1] = pw(fac[N-1],mod-2);
        for(ll i=N-1; i>0; i--){
                inv[i-1] = (inv[i]*i)%mod;
        }
        for(ll 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 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 Fenwick{
        ll fen[maxn];
        void upd(ll pos , ll val)
        {
                for(; pos<=n; pos+=(pos&-pos)){
                        fen[pos]=(fen[pos]+val)%mod;
                }
        }
        ll find(ll pos)
        {
                ll res = 0;
                for(; pos>0; pos-=(pos&-pos)){
                        res = (res+fen[pos])%mod;
                }
                return res;
        }
        ll ask(ll l , ll r)
        {
                return find(r)-find(l-1);
        }
 
};//ok
 
Segment Par;
Fenwick Sz , Val;
ll 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++){
                ll 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.upd(st[1],n);
        Val.upd(st[1],k);
        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;
                        X -= Val.ask(st[v],en[v]);
                        Val.upd(st[v],X);
                        ll siz=sz[v] - Sz.ask(st[v],en[v]);
                        Sz.upd(st[v],siz);
                        pll e = Par.ask(st[v]);ll p = e.S;
                        Par.upd({-h[v],v},st[v],en[v]);
                        Val.upd(st[p],-X);
                        Sz.upd(st[p],-siz);
                        
                        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;
                }else{
                        while(n){
                                cout<<"NO"<<endl;
                        }
                        ll v; cin>>v;
                        Par.del({-h[v],v},st[v],en[v]);
                        pll e = Par.ask(st[v]);ll p = e.S;
                        ll siz = Sz.ask(st[v],st[v]);
                        Val.upd(st[v],-temp[v]);
                        Val.upd(st[p],temp[v]);
                        Sz.upd(st[v],-siz);
                        Sz.upd(st[p],siz);
 
                        ll x = choose(temp[p]+cnt[p]-1 , cnt[p]-1);
                        ll y = choose(temp[v]+cnt[v]-1 , cnt[v]-1);
                        ans = (ans * pw(x,mod-2))%mod;
                        ans = (ans * pw(y,mod-2))%mod;
                        cnt[p] += siz;
                        cnt[v] -= siz;
                        temp[p] += temp[v];
                        temp[v] -= temp[v];
                        x = choose(temp[p]+cnt[p]-1 , cnt[p]-1);
                        ans = (ans * x)%mod;
                }
                ANS.push_back(ans);     
        }
        for(auto u : ANS){
                cout<<u<<"\n";
        }
        return 0;
}
/*
4 3
1 2
2 3
2 4
2
1 3 1
1 2 1
 
*/
/*
 
*/
/*
by
          _____                    _____                    _____                    _____                  
         /\    \                  /\    \                  /\    \                  /\    \                 
        /::\    \                /::\    \                /::\____\                /::\    \                
       /::::\    \              /::::\    \              /:::/    /                \:::\    \               
      /::::::\    \            /::::::\    \            /:::/    /                  \:::\    \              
     /:::/\:::\    \          /:::/\:::\    \          /:::/    /                    \:::\    \             
    /:::/__\:::\    \        /:::/__\:::\    \        /:::/____/                      \:::\    \            
   /::::\   \:::\    \       \:::\   \:::\    \      /::::\    \                      /::::\    \           
  /::::::\   \:::\    \    ___\:::\   \:::\    \    /::::::\    \   _____    ____    /::::::\    \          
 /:::/\:::\   \:::\    \  /\   \:::\   \:::\    \  /:::/\:::\    \ /\    \  /\   \  /:::/\:::\    \         
/:::/  \:::\   \:::\____\/::\   \:::\   \:::\____\/:::/  \:::\    /::\____\/::\   \/:::/  \:::\____\        
\::/    \:::\  /:::/    /\:::\   \:::\   \::/    /\::/    \:::\  /:::/    /\:::\  /:::/    \::/    /        
 \/____/ \:::\/:::/    /  \:::\   \:::\   \/____/  \/____/ \:::\/:::/    /  \:::\/:::/    / \/____/         
          \::::::/    /    \:::\   \:::\    \               \::::::/    /    \::::::/    /                  
           \::::/    /      \:::\   \:::\____\               \::::/    /      \::::/____/                   
           /:::/    /        \:::\  /:::/    /               /:::/    /        \:::\    \                   
          /:::/    /          \:::\/:::/    /               /:::/    /          \:::\    \                  
         /:::/    /            \::::::/    /               /:::/    /            \:::\    \                 
        /:::/    /              \::::/    /               /:::/    /              \:::\____\                
        \::/    /                \::/    /                \::/    /                \::/    /                
         \/____/                  \/____/                  \/____/                  \/____/                 
                                                                                                            
*/
//NOGHRE SHODANAM BAD NIST :_)

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 153 ms 128240 KB Output is correct
2 Correct 155 ms 128252 KB Output is correct
3 Correct 157 ms 128296 KB Output is correct
4 Correct 161 ms 128332 KB Output is correct
5 Correct 150 ms 122436 KB Output is correct
6 Correct 52 ms 82508 KB Output is correct
7 Correct 46 ms 82356 KB Output is correct
8 Correct 46 ms 82348 KB Output is correct
9 Correct 151 ms 119000 KB Output is correct
10 Correct 158 ms 118900 KB Output is correct
11 Correct 203 ms 118972 KB Output is correct
12 Correct 180 ms 117124 KB Output is correct
13 Correct 147 ms 124512 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3053 ms 91200 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 205 ms 137164 KB Output is correct
2 Correct 231 ms 144668 KB Output is correct
3 Correct 204 ms 138484 KB Output is correct
4 Correct 355 ms 157492 KB Output is correct
5 Correct 807 ms 208916 KB Output is correct
6 Correct 48 ms 83020 KB Output is correct
7 Correct 46 ms 82508 KB Output is correct
8 Correct 50 ms 82888 KB Output is correct
9 Correct 407 ms 138916 KB Output is correct
10 Correct 328 ms 135632 KB Output is correct
11 Correct 296 ms 134544 KB Output is correct
12 Correct 354 ms 136424 KB Output is correct
13 Correct 714 ms 259440 KB Output is correct
14 Correct 739 ms 259544 KB Output is correct
15 Correct 731 ms 259504 KB Output is correct
16 Correct 728 ms 259448 KB Output is correct
17 Correct 722 ms 259412 KB Output is correct

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3069 ms 132780 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 153 ms 128240 KB Output is correct
2 Correct 155 ms 128252 KB Output is correct
3 Correct 157 ms 128296 KB Output is correct
4 Correct 161 ms 128332 KB Output is correct
5 Correct 150 ms 122436 KB Output is correct
6 Correct 52 ms 82508 KB Output is correct
7 Correct 46 ms 82356 KB Output is correct
8 Correct 46 ms 82348 KB Output is correct
9 Correct 151 ms 119000 KB Output is correct
10 Correct 158 ms 118900 KB Output is correct
11 Correct 203 ms 118972 KB Output is correct
12 Correct 180 ms 117124 KB Output is correct
13 Correct 147 ms 124512 KB Output is correct
14 Execution timed out 3053 ms 91200 KB Time limit exceeded
15 Halted 0 ms 0 KB -