Submission #951678

#	Time	Username	Problem	Language	Result	Execution time	Memory
951678		Mohammadamin__Sh	Sumtree (INOI20_sumtree)	C++17	0 / 100	293 ms	194092 KiB

Main

//In His Name
#include <bits/stdc++.h>
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2")
using namespace std;
#define ll long long
#define int ll
typedef pair<int, int> pii;
#define F first
#define S second
#define pb push_back
#define bug(x) cout << "Ah shit , here we go again : " << x <<endl
#define all(x) x.begin() , x.end()
const int maxn = 3e5 + 10, MOD = 1e9 + 7;
const ll INF = 1e18 + 100;

int n , q , root , h[maxn] , st[maxn] , fn[maxn] , ti , val[maxn] , fact[maxn] , sub[maxn] , ans;
vector<int> adj[maxn];

void Dfs(int v , int p){
    st[v] = ++ti , h[v] = h[p]+1;
    for(int u : adj[v]) if(u != p) Dfs(u , v) , sub[v] += sub[u];
    sub[v] += adj[v].size();
    if(v != 1) sub[v]--;
    fn[v] = ti;
}

int Power(int x , int y){
    if(y == 0) return 1;
    int tmp = Power(x , y/2);
    tmp = tmp * tmp % MOD;
    if(y & 1) tmp = tmp * x % MOD;
    return tmp;
}

int Sayale(int x , int y){ // paeen bala
    return fact[x+y] * Power(fact[x] * fact[y] % MOD , MOD-2) % MOD;
}

struct FindPar{
    set<pii , greater<pii>> hoom[4*maxn];

    void Update(int id , int L , int R , int l , int r , int w , int ty){
        if(L == l and R == r) {
            if(ty == 0) hoom[id].erase({h[w] , w});
            else hoom[id].insert({h[w] , w});
            return;
        }
        int mid = (L+R) >> 1 , lc = id << 1 , rc = lc | 1;
        if(l < mid) Update(lc , L , mid , l , min(r, mid) , w , ty);
        if(r > mid) Update(rc , mid , R , max(l , mid) , r , w , ty);
    }

    int Get(int id , int L , int R , int idx , int v){
        int res = 0;
        if(hoom[id].size()) res = hoom[id].begin()->S;
        if(L + 1 == R) return res;
        int mid = (L+R) >> 1 , lc = id << 1 , rc = lc | 1 , res2;
        if(idx < mid) res2 = Get(lc , L , mid , idx , v);
        else res2 = Get(rc , mid , R , idx , v);
        return h[res] > h[res2] ? res : res2;
    }

}Find;


struct Segment{
    int toop[4*maxn] , sabad[4*maxn]; // barchasb - raas

    void Update(int id , int L , int R , int idx , int w , int ty){ // ty = 0 -> toop , ty = 1 -> sabad
        if(L+1 == R){
            ty == 0 ? toop[id] += w : sabad[id] += w;
            return;
        }
        int mid = (L+R) >> 1 , lc = id << 1 , rc = lc | 1;
        if(idx < mid) Update(lc , L , mid , idx , w , ty);
        else Update(rc , mid , R , idx , w , ty);
        toop[id] = toop[lc] + toop[rc];
        sabad[id] = sabad[lc] + sabad[rc];
    }

    pii Get(int id , int L , int R , int l , int r){
        if(L == l and R == r) return{toop[id] , sabad[id]};
        int mid = (L+R) >> 1 , lc = id << 1 , rc = lc | 1;
        pii res1 = {0,0} , res2 = {0 , 0};
        if(l < mid) res1 = Get(lc , L , mid , l , min(r , mid));
        if(r > mid) res2 = Get(rc , mid , R , max(l , mid) , r);
        return {res1.F + res2.F , res1.S + res2.S};
    }

}Seg;

int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0) , cout.tie(0);

    fact[0] = 1;
    for(int i = 1 ; i < maxn ; i++) fact[i] = fact[i-1] * i % MOD;
    cin >> n >> root;
    for(int i = 1 ; i < n ; i++){
        int u , v;
        cin >> u >> v;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    Dfs(1 , 0);
    cin >> q;
    ans = Sayale(sub[1] , root);
    val[1] = root;
    cout << ans << '\n';
    Find.Update(1 , 1 , n+1 , st[1] , fn[1]+1 , 1 , 1);
    Seg.Update(1 , 1 , n+1 , st[1] , root , 0);
    Seg.Update(1 , 1 , n+1 , st[1] , sub[1] , 1);
    while(q--){
        int ty , v , w;
        cin >> ty;
        if(ans <= 0) ans = 1;
        if(ty == 1){
            cin >> v >> w;
            val[v] = w;
            if(val[v] < 0){
                ans = 0;
                continue;
            }
            int par = Find.Get(1 , 1 , n+1 , st[v] , v);
            pii x = Seg.Get(1 , 1 , n+1 , st[v] , fn[v]+1);
            pii y = Seg.Get(1 , 1 , n+1 , st[par]+1 , fn[par]+1);
            ans = ans * Power(Sayale(sub[par]-y.S , val[par]-y.F) , MOD-2) % MOD;
            ans = ans * Sayale(sub[v] - x.S , val[v]-x.F) % MOD;
            Seg.Update(1 , 1 , n+1 , st[v] , val[v] - x.F , 0);
            Seg.Update(1 , 1 , n+1 , st[v] , sub[v] - x.S + 1 , 1);
            y = Seg.Get(1 , 1 , n+1 , st[par]+1 , fn[par]+1);
            ans = ans * Sayale(sub[par]-y.S , val[par]-y.F) % MOD;
            Find.Update(1 , 1 , n+1 , st[v] , fn[v]+1 , v , 1);
        }
        else{
            cin >> v;
            int par = Find.Get(1 , 1 , n+1 , st[v]-1 , v);
            pii x = Seg.Get(1 , 1 , n+1 , st[v]+1 , fn[v]+1);
            pii y = Seg.Get(1 , 1 , n+1 , st[par]+1 , fn[par]+1);
            ans = ans * Power(Sayale(sub[v]-x.S, val[v]-x.F) , MOD-2) % MOD;
            ans = ans * Power(Sayale(sub[par]-y.S , val[par]-y.F) , MOD-2) % MOD;
            Seg.Update(1 , 1 , n+1 , st[v] , -(sub[v] - x.F + 1) , 1);
            Seg.Update(1 , 1 , n+1 , st[v] , -(val[v] - x.S) , 0);
            val[v] = 0;
            y = Seg.Get(1 , 1 , n+1 , st[par]+1 , fn[par]+1);
            ans = ans * Sayale(sub[par]-y.S , val[par]-y.F) % MOD;
            Find.Update(1 , 1 , n+1 , st[v] , fn[v]+1 , v , 0);
        }
        cout << ans << '\n';
    }
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 30