oj.uz

Submission #809230

# Submission time Handle Problem Language Result Execution time Memory
809230 2023-08-05T22:58:39 Z ashcomp Sumtree (INOI20_sumtree) C++14
30 / 100
 830 ms 317600 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 = 6e5 + 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{
        ll fen[maxn];
        void upd(ll pos , ll val)
        {
                for(; pos<=n; pos+=(pos&-pos)){
                        fen[pos]+=val;
                }
        }
        ll find(ll pos)
        {
                ll res = 0;
                for(; pos>0; pos-=(pos&-pos)){
                        res += fen[pos];
                }
                return res;
        }
        ll ask(ll l , ll r)
        {
                return find(r)-find(l-1);
        }

};//ok

PAR_segment Par;
SZ_segment Sz , Val;
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.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);
                        //cout<<p<<" , "<<siz<<" , "<<X<<"\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);
                        /**/
                }else{
                        int v; cin>>v;
                        Par.del({-h[v],v},st[v],en[v]);
                        pll e = Par.ask(st[v]);ll p = e.S;
                        ll siz = cnt[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);
                        x = (y*x);
                        ans = (ans * pw(x,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);
                        /**/
                }
        }
        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

# Verdict Execution time Memory Grader output
1 Correct 171 ms 187800 KB Output is correct
2 Correct 187 ms 187772 KB Output is correct
3 Correct 175 ms 187776 KB Output is correct
4 Correct 171 ms 187724 KB Output is correct
5 Correct 165 ms 181956 KB Output is correct
6 Correct 65 ms 142012 KB Output is correct
7 Correct 74 ms 141744 KB Output is correct
8 Correct 69 ms 141916 KB Output is correct
9 Correct 211 ms 178512 KB Output is correct
10 Correct 164 ms 178292 KB Output is correct
11 Correct 173 ms 178508 KB Output is correct
12 Correct 179 ms 176720 KB Output is correct
13 Correct 164 ms 184012 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 141148 KB Output is correct
2 Correct 63 ms 141188 KB Output is correct
3 Correct 63 ms 141204 KB Output is correct
4 Incorrect 63 ms 141216 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 195176 KB Output is correct
2 Correct 244 ms 202528 KB Output is correct
3 Correct 222 ms 196364 KB Output is correct
4 Correct 341 ms 215512 KB Output is correct
5 Correct 830 ms 266840 KB Output is correct
6 Correct 67 ms 142448 KB Output is correct
7 Correct 66 ms 141980 KB Output is correct
8 Correct 79 ms 142292 KB Output is correct
9 Correct 360 ms 196908 KB Output is correct
10 Correct 351 ms 193660 KB Output is correct
11 Correct 308 ms 192476 KB Output is correct
12 Correct 371 ms 194396 KB Output is correct
13 Correct 702 ms 317600 KB Output is correct
14 Correct 707 ms 317468 KB Output is correct
15 Correct 697 ms 317556 KB Output is correct
16 Correct 704 ms 317488 KB Output is correct
17 Correct 706 ms 317392 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 460 ms 186936 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 187800 KB Output is correct
2 Correct 187 ms 187772 KB Output is correct
3 Correct 175 ms 187776 KB Output is correct
4 Correct 171 ms 187724 KB Output is correct
5 Correct 165 ms 181956 KB Output is correct
6 Correct 65 ms 142012 KB Output is correct
7 Correct 74 ms 141744 KB Output is correct
8 Correct 69 ms 141916 KB Output is correct
9 Correct 211 ms 178512 KB Output is correct
10 Correct 164 ms 178292 KB Output is correct
11 Correct 173 ms 178508 KB Output is correct
12 Correct 179 ms 176720 KB Output is correct
13 Correct 164 ms 184012 KB Output is correct
14 Correct 65 ms 141148 KB Output is correct
15 Correct 63 ms 141188 KB Output is correct
16 Correct 63 ms 141204 KB Output is correct
17 Incorrect 63 ms 141216 KB Output isn't correct
18 Halted 0 ms 0 KB -