oj.uz

Submission #809240

# Submission time Handle Problem Language Result Execution time Memory
809240 2023-08-05T23:28:17 Z ashcomp Sumtree (INOI20_sumtree) C++14
50 / 100
 839 ms 259576 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;
                }
                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 154 ms 128308 KB Output is correct
2 Correct 165 ms 128268 KB Output is correct
3 Correct 176 ms 128196 KB Output is correct
4 Correct 160 ms 128288 KB Output is correct
5 Correct 159 ms 122532 KB Output is correct
6 Correct 47 ms 82556 KB Output is correct
7 Correct 46 ms 82280 KB Output is correct
8 Correct 46 ms 82396 KB Output is correct
9 Correct 163 ms 119000 KB Output is correct
10 Correct 165 ms 118836 KB Output is correct
11 Correct 160 ms 119056 KB Output is correct
12 Correct 151 ms 117200 KB Output is correct
13 Correct 146 ms 124660 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 81740 KB Output is correct
2 Correct 46 ms 81692 KB Output is correct
3 Correct 51 ms 81716 KB Output is correct
4 Correct 46 ms 81688 KB Output is correct
5 Correct 47 ms 81832 KB Output is correct
6 Correct 48 ms 82380 KB Output is correct
7 Correct 51 ms 82276 KB Output is correct
8 Correct 48 ms 82252 KB Output is correct
9 Correct 49 ms 82508 KB Output is correct
10 Correct 50 ms 82708 KB Output is correct
11 Correct 50 ms 82824 KB Output is correct
12 Correct 46 ms 82588 KB Output is correct
13 Correct 51 ms 82720 KB Output is correct
14 Correct 51 ms 82632 KB Output is correct
15 Correct 53 ms 82928 KB Output is correct
16 Correct 49 ms 82508 KB Output is correct
17 Correct 55 ms 82728 KB Output is correct
18 Correct 50 ms 82312 KB Output is correct
19 Correct 53 ms 82564 KB Output is correct
20 Correct 51 ms 82216 KB Output is correct
21 Correct 48 ms 82304 KB Output is correct
22 Correct 47 ms 81900 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 137188 KB Output is correct
2 Correct 238 ms 144644 KB Output is correct
3 Correct 212 ms 138516 KB Output is correct
4 Correct 327 ms 157412 KB Output is correct
5 Correct 839 ms 208908 KB Output is correct
6 Correct 49 ms 83020 KB Output is correct
7 Correct 48 ms 82516 KB Output is correct
8 Correct 51 ms 82932 KB Output is correct
9 Correct 368 ms 138884 KB Output is correct
10 Correct 348 ms 135664 KB Output is correct
11 Correct 291 ms 134468 KB Output is correct
12 Correct 377 ms 136388 KB Output is correct
13 Correct 714 ms 259468 KB Output is correct
14 Correct 744 ms 259492 KB Output is correct
15 Correct 730 ms 259496 KB Output is correct
16 Correct 741 ms 259576 KB Output is correct
17 Correct 741 ms 259456 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 474 ms 129024 KB Output is correct
2 Correct 493 ms 128768 KB Output is correct
3 Correct 470 ms 128936 KB Output is correct
4 Correct 471 ms 128976 KB Output is correct
5 Correct 443 ms 126520 KB Output is correct
6 Correct 474 ms 128940 KB Output is correct
7 Correct 380 ms 107228 KB Output is correct
8 Correct 350 ms 107312 KB Output is correct
9 Correct 515 ms 129068 KB Output is correct
10 Correct 443 ms 128964 KB Output is correct
11 Correct 450 ms 128904 KB Output is correct
12 Correct 357 ms 107180 KB Output is correct
13 Incorrect 252 ms 103208 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 128308 KB Output is correct
2 Correct 165 ms 128268 KB Output is correct
3 Correct 176 ms 128196 KB Output is correct
4 Correct 160 ms 128288 KB Output is correct
5 Correct 159 ms 122532 KB Output is correct
6 Correct 47 ms 82556 KB Output is correct
7 Correct 46 ms 82280 KB Output is correct
8 Correct 46 ms 82396 KB Output is correct
9 Correct 163 ms 119000 KB Output is correct
10 Correct 165 ms 118836 KB Output is correct
11 Correct 160 ms 119056 KB Output is correct
12 Correct 151 ms 117200 KB Output is correct
13 Correct 146 ms 124660 KB Output is correct
14 Correct 46 ms 81740 KB Output is correct
15 Correct 46 ms 81692 KB Output is correct
16 Correct 51 ms 81716 KB Output is correct
17 Correct 46 ms 81688 KB Output is correct
18 Correct 47 ms 81832 KB Output is correct
19 Correct 48 ms 82380 KB Output is correct
20 Correct 51 ms 82276 KB Output is correct
21 Correct 48 ms 82252 KB Output is correct
22 Correct 49 ms 82508 KB Output is correct
23 Correct 50 ms 82708 KB Output is correct
24 Correct 50 ms 82824 KB Output is correct
25 Correct 46 ms 82588 KB Output is correct
26 Correct 51 ms 82720 KB Output is correct
27 Correct 51 ms 82632 KB Output is correct
28 Correct 53 ms 82928 KB Output is correct
29 Correct 49 ms 82508 KB Output is correct
30 Correct 55 ms 82728 KB Output is correct
31 Correct 50 ms 82312 KB Output is correct
32 Correct 53 ms 82564 KB Output is correct
33 Correct 51 ms 82216 KB Output is correct
34 Correct 48 ms 82304 KB Output is correct
35 Correct 47 ms 81900 KB Output is correct
36 Correct 208 ms 137188 KB Output is correct
37 Correct 238 ms 144644 KB Output is correct
38 Correct 212 ms 138516 KB Output is correct
39 Correct 327 ms 157412 KB Output is correct
40 Correct 839 ms 208908 KB Output is correct
41 Correct 49 ms 83020 KB Output is correct
42 Correct 48 ms 82516 KB Output is correct
43 Correct 51 ms 82932 KB Output is correct
44 Correct 368 ms 138884 KB Output is correct
45 Correct 348 ms 135664 KB Output is correct
46 Correct 291 ms 134468 KB Output is correct
47 Correct 377 ms 136388 KB Output is correct
48 Correct 714 ms 259468 KB Output is correct
49 Correct 744 ms 259492 KB Output is correct
50 Correct 730 ms 259496 KB Output is correct
51 Correct 741 ms 259576 KB Output is correct
52 Correct 741 ms 259456 KB Output is correct
53 Correct 474 ms 129024 KB Output is correct
54 Correct 493 ms 128768 KB Output is correct
55 Correct 470 ms 128936 KB Output is correct
56 Correct 471 ms 128976 KB Output is correct
57 Correct 443 ms 126520 KB Output is correct
58 Correct 474 ms 128940 KB Output is correct
59 Correct 380 ms 107228 KB Output is correct
60 Correct 350 ms 107312 KB Output is correct
61 Correct 515 ms 129068 KB Output is correct
62 Correct 443 ms 128964 KB Output is correct
63 Correct 450 ms 128904 KB Output is correct
64 Correct 357 ms 107180 KB Output is correct
65 Incorrect 252 ms 103208 KB Output isn't correct
66 Halted 0 ms 0 KB -