oj.uz

Submission #809229

# Submission time Handle Problem Language Result Execution time Memory
809229 2023-08-05T22:54:29 Z ashcomp Sumtree (INOI20_sumtree) C++14
30 / 100
 852 ms 326372 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{
        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[v],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);
                        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);
                        /**/
                }
        }
        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 179 ms 164248 KB Output is correct
2 Correct 169 ms 164256 KB Output is correct
3 Correct 173 ms 164388 KB Output is correct
4 Correct 158 ms 164280 KB Output is correct
5 Correct 179 ms 158484 KB Output is correct
6 Correct 56 ms 118596 KB Output is correct
7 Correct 56 ms 118328 KB Output is correct
8 Correct 58 ms 118364 KB Output is correct
9 Correct 169 ms 155012 KB Output is correct
10 Correct 157 ms 154924 KB Output is correct
11 Correct 199 ms 154992 KB Output is correct
12 Correct 169 ms 153256 KB Output is correct
13 Correct 148 ms 160588 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 117712 KB Output is correct
2 Incorrect 54 ms 117740 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 237 ms 171748 KB Output is correct
2 Correct 250 ms 181800 KB Output is correct
3 Correct 232 ms 175484 KB Output is correct
4 Correct 342 ms 194920 KB Output is correct
5 Correct 852 ms 247244 KB Output is correct
6 Correct 57 ms 118988 KB Output is correct
7 Correct 56 ms 118432 KB Output is correct
8 Correct 58 ms 118948 KB Output is correct
9 Correct 372 ms 176752 KB Output is correct
10 Correct 335 ms 173408 KB Output is correct
11 Correct 314 ms 172284 KB Output is correct
12 Correct 333 ms 174524 KB Output is correct
13 Correct 703 ms 299440 KB Output is correct
14 Correct 706 ms 299408 KB Output is correct
15 Correct 728 ms 299436 KB Output is correct
16 Correct 694 ms 299392 KB Output is correct
17 Correct 745 ms 299340 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 445 ms 326372 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 164248 KB Output is correct
2 Correct 169 ms 164256 KB Output is correct
3 Correct 173 ms 164388 KB Output is correct
4 Correct 158 ms 164280 KB Output is correct
5 Correct 179 ms 158484 KB Output is correct
6 Correct 56 ms 118596 KB Output is correct
7 Correct 56 ms 118328 KB Output is correct
8 Correct 58 ms 118364 KB Output is correct
9 Correct 169 ms 155012 KB Output is correct
10 Correct 157 ms 154924 KB Output is correct
11 Correct 199 ms 154992 KB Output is correct
12 Correct 169 ms 153256 KB Output is correct
13 Correct 148 ms 160588 KB Output is correct
14 Correct 53 ms 117712 KB Output is correct
15 Incorrect 54 ms 117740 KB Output isn't correct
16 Halted 0 ms 0 KB -