oj.uz

Submission #809237

# Submission time Handle Problem Language Result Execution time Memory
809237 2023-08-05T23:13:12 Z ashcomp Sumtree (INOI20_sumtree) C++14
10 / 100
 3000 ms 208988 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{
                        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;
                }
                if(ans <= 0){
                        while(ans <= 0){
                                cout<<"NOnnnnnnnnnn"<<endl;
                        }
                }
                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 156 ms 128208 KB Output is correct
2 Correct 170 ms 128352 KB Output is correct
3 Correct 180 ms 128284 KB Output is correct
4 Correct 154 ms 128176 KB Output is correct
5 Correct 152 ms 122552 KB Output is correct
6 Correct 47 ms 82556 KB Output is correct
7 Correct 47 ms 82308 KB Output is correct
8 Correct 46 ms 82380 KB Output is correct
9 Correct 163 ms 118988 KB Output is correct
10 Correct 157 ms 118892 KB Output is correct
11 Correct 159 ms 118956 KB Output is correct
12 Correct 145 ms 117156 KB Output is correct
13 Correct 143 ms 124480 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 81676 KB Output is correct
2 Correct 49 ms 81976 KB Output is correct
3 Correct 46 ms 81776 KB Output is correct
4 Correct 45 ms 81748 KB Output is correct
5 Correct 46 ms 81816 KB Output is correct
6 Correct 48 ms 82272 KB Output is correct
7 Correct 48 ms 82268 KB Output is correct
8 Correct 48 ms 82264 KB Output is correct
9 Correct 51 ms 82524 KB Output is correct
10 Correct 51 ms 82748 KB Output is correct
11 Correct 53 ms 82804 KB Output is correct
12 Correct 48 ms 82596 KB Output is correct
13 Correct 52 ms 82628 KB Output is correct
14 Correct 52 ms 82724 KB Output is correct
15 Correct 52 ms 82892 KB Output is correct
16 Correct 50 ms 82544 KB Output is correct
17 Correct 51 ms 82648 KB Output is correct
18 Correct 51 ms 82288 KB Output is correct
19 Correct 49 ms 82528 KB Output is correct
20 Execution timed out 3081 ms 123416 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 202 ms 137268 KB Output is correct
2 Correct 242 ms 144596 KB Output is correct
3 Correct 209 ms 138444 KB Output is correct
4 Correct 331 ms 157512 KB Output is correct
5 Correct 770 ms 208988 KB Output is correct
6 Correct 49 ms 83024 KB Output is correct
7 Correct 48 ms 82452 KB Output is correct
8 Correct 50 ms 82812 KB Output is correct
9 Correct 362 ms 138824 KB Output is correct
10 Correct 324 ms 135656 KB Output is correct
11 Correct 294 ms 134504 KB Output is correct
12 Execution timed out 3063 ms 158792 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 468 ms 129088 KB Output is correct
2 Correct 462 ms 128688 KB Output is correct
3 Correct 462 ms 128976 KB Output is correct
4 Correct 467 ms 128952 KB Output is correct
5 Correct 443 ms 126528 KB Output is correct
6 Correct 458 ms 128920 KB Output is correct
7 Correct 350 ms 107268 KB Output is correct
8 Correct 361 ms 107484 KB Output is correct
9 Correct 476 ms 129056 KB Output is correct
10 Correct 446 ms 128900 KB Output is correct
11 Correct 456 ms 128924 KB Output is correct
12 Correct 353 ms 107204 KB Output is correct
13 Execution timed out 3082 ms 141104 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 128208 KB Output is correct
2 Correct 170 ms 128352 KB Output is correct
3 Correct 180 ms 128284 KB Output is correct
4 Correct 154 ms 128176 KB Output is correct
5 Correct 152 ms 122552 KB Output is correct
6 Correct 47 ms 82556 KB Output is correct
7 Correct 47 ms 82308 KB Output is correct
8 Correct 46 ms 82380 KB Output is correct
9 Correct 163 ms 118988 KB Output is correct
10 Correct 157 ms 118892 KB Output is correct
11 Correct 159 ms 118956 KB Output is correct
12 Correct 145 ms 117156 KB Output is correct
13 Correct 143 ms 124480 KB Output is correct
14 Correct 45 ms 81676 KB Output is correct
15 Correct 49 ms 81976 KB Output is correct
16 Correct 46 ms 81776 KB Output is correct
17 Correct 45 ms 81748 KB Output is correct
18 Correct 46 ms 81816 KB Output is correct
19 Correct 48 ms 82272 KB Output is correct
20 Correct 48 ms 82268 KB Output is correct
21 Correct 48 ms 82264 KB Output is correct
22 Correct 51 ms 82524 KB Output is correct
23 Correct 51 ms 82748 KB Output is correct
24 Correct 53 ms 82804 KB Output is correct
25 Correct 48 ms 82596 KB Output is correct
26 Correct 52 ms 82628 KB Output is correct
27 Correct 52 ms 82724 KB Output is correct
28 Correct 52 ms 82892 KB Output is correct
29 Correct 50 ms 82544 KB Output is correct
30 Correct 51 ms 82648 KB Output is correct
31 Correct 51 ms 82288 KB Output is correct
32 Correct 49 ms 82528 KB Output is correct
33 Execution timed out 3081 ms 123416 KB Time limit exceeded
34 Halted 0 ms 0 KB -