oj.uz

Submission #809231

# Submission time Handle Problem Language Result Execution time Memory
809231 2023-08-05T22:59:54 Z ashcomp Sumtree (INOI20_sumtree) C++14
50 / 100
 835 ms 317604 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)%mod;
                        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 179 ms 187836 KB Output is correct
2 Correct 181 ms 187716 KB Output is correct
3 Correct 179 ms 187724 KB Output is correct
4 Correct 170 ms 187788 KB Output is correct
5 Correct 162 ms 181996 KB Output is correct
6 Correct 69 ms 142032 KB Output is correct
7 Correct 66 ms 141828 KB Output is correct
8 Correct 70 ms 141804 KB Output is correct
9 Correct 174 ms 178548 KB Output is correct
10 Correct 166 ms 178304 KB Output is correct
11 Correct 184 ms 178520 KB Output is correct
12 Correct 164 ms 176724 KB Output is correct
13 Correct 157 ms 184012 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 141260 KB Output is correct
2 Correct 66 ms 141336 KB Output is correct
3 Correct 65 ms 141220 KB Output is correct
4 Correct 69 ms 141260 KB Output is correct
5 Correct 69 ms 141388 KB Output is correct
6 Correct 70 ms 141836 KB Output is correct
7 Correct 65 ms 141740 KB Output is correct
8 Correct 68 ms 141832 KB Output is correct
9 Correct 70 ms 142028 KB Output is correct
10 Correct 74 ms 142328 KB Output is correct
11 Correct 69 ms 142324 KB Output is correct
12 Correct 67 ms 142012 KB Output is correct
13 Correct 69 ms 142244 KB Output is correct
14 Correct 70 ms 142252 KB Output is correct
15 Correct 69 ms 142440 KB Output is correct
16 Correct 66 ms 142068 KB Output is correct
17 Correct 69 ms 142240 KB Output is correct
18 Correct 68 ms 141776 KB Output is correct
19 Correct 67 ms 142036 KB Output is correct
20 Correct 68 ms 141740 KB Output is correct
21 Correct 65 ms 141816 KB Output is correct
22 Correct 64 ms 141396 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 195168 KB Output is correct
2 Correct 245 ms 202648 KB Output is correct
3 Correct 225 ms 196428 KB Output is correct
4 Correct 342 ms 215396 KB Output is correct
5 Correct 777 ms 266924 KB Output is correct
6 Correct 74 ms 142428 KB Output is correct
7 Correct 67 ms 141992 KB Output is correct
8 Correct 68 ms 142368 KB Output is correct
9 Correct 375 ms 196832 KB Output is correct
10 Correct 329 ms 193656 KB Output is correct
11 Correct 325 ms 192520 KB Output is correct
12 Correct 339 ms 194396 KB Output is correct
13 Correct 721 ms 317424 KB Output is correct
14 Correct 835 ms 317496 KB Output is correct
15 Correct 725 ms 317480 KB Output is correct
16 Correct 716 ms 317604 KB Output is correct
17 Correct 698 ms 317376 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 435 ms 186860 KB Output is correct
2 Correct 430 ms 191212 KB Output is correct
3 Correct 434 ms 191416 KB Output is correct
4 Correct 437 ms 191392 KB Output is correct
5 Correct 444 ms 188860 KB Output is correct
6 Correct 450 ms 191232 KB Output is correct
7 Correct 327 ms 168820 KB Output is correct
8 Correct 332 ms 169056 KB Output is correct
9 Correct 482 ms 191416 KB Output is correct
10 Correct 416 ms 191356 KB Output is correct
11 Correct 452 ms 191540 KB Output is correct
12 Correct 325 ms 169052 KB Output is correct
13 Incorrect 238 ms 165836 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 187836 KB Output is correct
2 Correct 181 ms 187716 KB Output is correct
3 Correct 179 ms 187724 KB Output is correct
4 Correct 170 ms 187788 KB Output is correct
5 Correct 162 ms 181996 KB Output is correct
6 Correct 69 ms 142032 KB Output is correct
7 Correct 66 ms 141828 KB Output is correct
8 Correct 70 ms 141804 KB Output is correct
9 Correct 174 ms 178548 KB Output is correct
10 Correct 166 ms 178304 KB Output is correct
11 Correct 184 ms 178520 KB Output is correct
12 Correct 164 ms 176724 KB Output is correct
13 Correct 157 ms 184012 KB Output is correct
14 Correct 65 ms 141260 KB Output is correct
15 Correct 66 ms 141336 KB Output is correct
16 Correct 65 ms 141220 KB Output is correct
17 Correct 69 ms 141260 KB Output is correct
18 Correct 69 ms 141388 KB Output is correct
19 Correct 70 ms 141836 KB Output is correct
20 Correct 65 ms 141740 KB Output is correct
21 Correct 68 ms 141832 KB Output is correct
22 Correct 70 ms 142028 KB Output is correct
23 Correct 74 ms 142328 KB Output is correct
24 Correct 69 ms 142324 KB Output is correct
25 Correct 67 ms 142012 KB Output is correct
26 Correct 69 ms 142244 KB Output is correct
27 Correct 70 ms 142252 KB Output is correct
28 Correct 69 ms 142440 KB Output is correct
29 Correct 66 ms 142068 KB Output is correct
30 Correct 69 ms 142240 KB Output is correct
31 Correct 68 ms 141776 KB Output is correct
32 Correct 67 ms 142036 KB Output is correct
33 Correct 68 ms 141740 KB Output is correct
34 Correct 65 ms 141816 KB Output is correct
35 Correct 64 ms 141396 KB Output is correct
36 Correct 220 ms 195168 KB Output is correct
37 Correct 245 ms 202648 KB Output is correct
38 Correct 225 ms 196428 KB Output is correct
39 Correct 342 ms 215396 KB Output is correct
40 Correct 777 ms 266924 KB Output is correct
41 Correct 74 ms 142428 KB Output is correct
42 Correct 67 ms 141992 KB Output is correct
43 Correct 68 ms 142368 KB Output is correct
44 Correct 375 ms 196832 KB Output is correct
45 Correct 329 ms 193656 KB Output is correct
46 Correct 325 ms 192520 KB Output is correct
47 Correct 339 ms 194396 KB Output is correct
48 Correct 721 ms 317424 KB Output is correct
49 Correct 835 ms 317496 KB Output is correct
50 Correct 725 ms 317480 KB Output is correct
51 Correct 716 ms 317604 KB Output is correct
52 Correct 698 ms 317376 KB Output is correct
53 Correct 435 ms 186860 KB Output is correct
54 Correct 430 ms 191212 KB Output is correct
55 Correct 434 ms 191416 KB Output is correct
56 Correct 437 ms 191392 KB Output is correct
57 Correct 444 ms 188860 KB Output is correct
58 Correct 450 ms 191232 KB Output is correct
59 Correct 327 ms 168820 KB Output is correct
60 Correct 332 ms 169056 KB Output is correct
61 Correct 482 ms 191416 KB Output is correct
62 Correct 416 ms 191356 KB Output is correct
63 Correct 452 ms 191540 KB Output is correct
64 Correct 325 ms 169052 KB Output is correct
65 Incorrect 238 ms 165836 KB Output isn't correct
66 Halted 0 ms 0 KB -