답안 #809237

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
809237	2023-08-05T23:13:12 Z	ashcomp	Sumtree (INOI20_sumtree)	C++14	10 / 100	3000 ms	208988 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];

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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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	-