Submission #809246

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
809246	2023-08-05T23:53:55 Z	ashcomp	Sumtree (INOI20_sumtree)	C++14	100 / 100	793 ms	259612 KB

Main

#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] , rest , Cnt;
bool mark[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);
        rest = ans;
        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);
                        if(x==0){
                                Cnt--;
                                mark[p] = 0;
                        }else{
                                rest = (rest * pw(x,mod-2))%mod;
                        }
                        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);
                        if(x==0){
                                Cnt++;
                                mark[p] = 1;
                        }else{
                                rest = (rest*x)%mod;
                        }
                        ans = (ans * x)%mod;
                        x = choose(temp[v]+cnt[v]-1 , cnt[v]-1);
                        if(x==0){
                                Cnt++;
                                mark[v] = 1;
                        }else{
                                rest = (rest * x)%mod;
                        }
                        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);
                        if(x==0){
                                Cnt--;
                                mark[p]=0;
                        }else{
                                rest = (rest * pw(x,mod-2))%mod;
                        }
                        ll y = choose(temp[v]+cnt[v]-1 , cnt[v]-1);
                        if(y==0){
                                Cnt--;
                                mark[v] = 0;
                        }else{
                                rest = (rest * pw(y,mod-2))%mod;
                        }
                        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);
                        if(x==0){
                                Cnt++;
                                mark[x] = 1;
                        }else{
                                rest = (rest * x)%mod;
                        }
                        ans = (ans * x)%mod;
                        
                }
                if(Cnt==0){
                        ans = rest;
                }
                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	161 ms	128264 KB	Output is correct
2	Correct	163 ms	128316 KB	Output is correct
3	Correct	160 ms	128300 KB	Output is correct
4	Correct	152 ms	128320 KB	Output is correct
5	Correct	146 ms	122552 KB	Output is correct
6	Correct	46 ms	82608 KB	Output is correct
7	Correct	46 ms	82256 KB	Output is correct
8	Correct	45 ms	82376 KB	Output is correct
9	Correct	170 ms	119124 KB	Output is correct
10	Correct	169 ms	118880 KB	Output is correct
11	Correct	154 ms	119088 KB	Output is correct
12	Correct	142 ms	117172 KB	Output is correct
13	Correct	146 ms	124572 KB	Output is correct

Subtask #2

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	46 ms	81728 KB	Output is correct
2	Correct	44 ms	81688 KB	Output is correct
3	Correct	44 ms	81784 KB	Output is correct
4	Correct	44 ms	81728 KB	Output is correct
5	Correct	46 ms	81888 KB	Output is correct
6	Correct	54 ms	82324 KB	Output is correct
7	Correct	47 ms	82240 KB	Output is correct
8	Correct	48 ms	82396 KB	Output is correct
9	Correct	51 ms	82568 KB	Output is correct
10	Correct	50 ms	82764 KB	Output is correct
11	Correct	58 ms	82836 KB	Output is correct
12	Correct	48 ms	82536 KB	Output is correct
13	Correct	50 ms	82636 KB	Output is correct
14	Correct	56 ms	82692 KB	Output is correct
15	Correct	57 ms	82872 KB	Output is correct
16	Correct	53 ms	82524 KB	Output is correct
17	Correct	50 ms	82720 KB	Output is correct
18	Correct	48 ms	82252 KB	Output is correct
19	Correct	49 ms	82524 KB	Output is correct
20	Correct	48 ms	82296 KB	Output is correct
21	Correct	47 ms	82228 KB	Output is correct
22	Correct	46 ms	81868 KB	Output is correct

Subtask #3

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	203 ms	137304 KB	Output is correct
2	Correct	230 ms	144712 KB	Output is correct
3	Correct	260 ms	138556 KB	Output is correct
4	Correct	341 ms	157444 KB	Output is correct
5	Correct	793 ms	208980 KB	Output is correct
6	Correct	47 ms	83012 KB	Output is correct
7	Correct	47 ms	82480 KB	Output is correct
8	Correct	48 ms	82900 KB	Output is correct
9	Correct	410 ms	139028 KB	Output is correct
10	Correct	399 ms	135744 KB	Output is correct
11	Correct	315 ms	134536 KB	Output is correct
12	Correct	346 ms	136596 KB	Output is correct
13	Correct	756 ms	259488 KB	Output is correct
14	Correct	730 ms	259612 KB	Output is correct
15	Correct	747 ms	259568 KB	Output is correct
16	Correct	736 ms	259492 KB	Output is correct
17	Correct	737 ms	259540 KB	Output is correct

Subtask #4

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	562 ms	128984 KB	Output is correct
2	Correct	545 ms	128828 KB	Output is correct
3	Correct	518 ms	128896 KB	Output is correct
4	Correct	509 ms	128964 KB	Output is correct
5	Correct	562 ms	126592 KB	Output is correct
6	Correct	504 ms	128948 KB	Output is correct
7	Correct	406 ms	107260 KB	Output is correct
8	Correct	401 ms	107372 KB	Output is correct
9	Correct	512 ms	129024 KB	Output is correct
10	Correct	505 ms	128912 KB	Output is correct
11	Correct	500 ms	128896 KB	Output is correct
12	Correct	399 ms	107204 KB	Output is correct
13	Correct	267 ms	103160 KB	Output is correct
14	Correct	301 ms	108448 KB	Output is correct
15	Correct	332 ms	108920 KB	Output is correct

Subtask #5

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	161 ms	128264 KB	Output is correct
2	Correct	163 ms	128316 KB	Output is correct
3	Correct	160 ms	128300 KB	Output is correct
4	Correct	152 ms	128320 KB	Output is correct
5	Correct	146 ms	122552 KB	Output is correct
6	Correct	46 ms	82608 KB	Output is correct
7	Correct	46 ms	82256 KB	Output is correct
8	Correct	45 ms	82376 KB	Output is correct
9	Correct	170 ms	119124 KB	Output is correct
10	Correct	169 ms	118880 KB	Output is correct
11	Correct	154 ms	119088 KB	Output is correct
12	Correct	142 ms	117172 KB	Output is correct
13	Correct	146 ms	124572 KB	Output is correct
14	Correct	46 ms	81728 KB	Output is correct
15	Correct	44 ms	81688 KB	Output is correct
16	Correct	44 ms	81784 KB	Output is correct
17	Correct	44 ms	81728 KB	Output is correct
18	Correct	46 ms	81888 KB	Output is correct
19	Correct	54 ms	82324 KB	Output is correct
20	Correct	47 ms	82240 KB	Output is correct
21	Correct	48 ms	82396 KB	Output is correct
22	Correct	51 ms	82568 KB	Output is correct
23	Correct	50 ms	82764 KB	Output is correct
24	Correct	58 ms	82836 KB	Output is correct
25	Correct	48 ms	82536 KB	Output is correct
26	Correct	50 ms	82636 KB	Output is correct
27	Correct	56 ms	82692 KB	Output is correct
28	Correct	57 ms	82872 KB	Output is correct
29	Correct	53 ms	82524 KB	Output is correct
30	Correct	50 ms	82720 KB	Output is correct
31	Correct	48 ms	82252 KB	Output is correct
32	Correct	49 ms	82524 KB	Output is correct
33	Correct	48 ms	82296 KB	Output is correct
34	Correct	47 ms	82228 KB	Output is correct
35	Correct	46 ms	81868 KB	Output is correct
36	Correct	203 ms	137304 KB	Output is correct
37	Correct	230 ms	144712 KB	Output is correct
38	Correct	260 ms	138556 KB	Output is correct
39	Correct	341 ms	157444 KB	Output is correct
40	Correct	793 ms	208980 KB	Output is correct
41	Correct	47 ms	83012 KB	Output is correct
42	Correct	47 ms	82480 KB	Output is correct
43	Correct	48 ms	82900 KB	Output is correct
44	Correct	410 ms	139028 KB	Output is correct
45	Correct	399 ms	135744 KB	Output is correct
46	Correct	315 ms	134536 KB	Output is correct
47	Correct	346 ms	136596 KB	Output is correct
48	Correct	756 ms	259488 KB	Output is correct
49	Correct	730 ms	259612 KB	Output is correct
50	Correct	747 ms	259568 KB	Output is correct
51	Correct	736 ms	259492 KB	Output is correct
52	Correct	737 ms	259540 KB	Output is correct
53	Correct	562 ms	128984 KB	Output is correct
54	Correct	545 ms	128828 KB	Output is correct
55	Correct	518 ms	128896 KB	Output is correct
56	Correct	509 ms	128964 KB	Output is correct
57	Correct	562 ms	126592 KB	Output is correct
58	Correct	504 ms	128948 KB	Output is correct
59	Correct	406 ms	107260 KB	Output is correct
60	Correct	401 ms	107372 KB	Output is correct
61	Correct	512 ms	129024 KB	Output is correct
62	Correct	505 ms	128912 KB	Output is correct
63	Correct	500 ms	128896 KB	Output is correct
64	Correct	399 ms	107204 KB	Output is correct
65	Correct	267 ms	103160 KB	Output is correct
66	Correct	301 ms	108448 KB	Output is correct
67	Correct	332 ms	108920 KB	Output is correct
68	Correct	45 ms	81696 KB	Output is correct
69	Correct	47 ms	81704 KB	Output is correct
70	Correct	574 ms	142896 KB	Output is correct
71	Correct	581 ms	142904 KB	Output is correct
72	Correct	570 ms	142844 KB	Output is correct
73	Correct	593 ms	142840 KB	Output is correct
74	Correct	735 ms	143264 KB	Output is correct
75	Correct	646 ms	137888 KB	Output is correct
76	Correct	475 ms	133420 KB	Output is correct
77	Correct	588 ms	134208 KB	Output is correct
78	Correct	615 ms	137784 KB	Output is correct
79	Correct	588 ms	138164 KB	Output is correct
80	Correct	655 ms	136276 KB	Output is correct
81	Correct	618 ms	137988 KB	Output is correct
82	Correct	357 ms	128136 KB	Output is correct
83	Correct	397 ms	136376 KB	Output is correct
84	Correct	420 ms	135612 KB	Output is correct
85	Correct	426 ms	135572 KB	Output is correct