Submission #635511

#	Time	Username	Problem	Language	Result	Execution time	Memory
635511		K4YAN	Sumtree (INOI20_sumtree)	C++17	100 / 100	1577 ms	280716 KiB

Main

//Be Name Khoda

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
#define pii pair<int, int>
#define pll pair<ll, ll>
#define plll pair<ll, pll>
#define all(x) x.begin(), x.end()
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>

const ll mxn = 2e5 + 16, MX = 3e5 + 16, md = 1e9 + 7;
ll n, r, t, q, w, cnt, pw;
ll st[mxn], ft[mxn], dp[mxn], h[mxn], subt[mxn], R[mxn], fact[MX + mxn], taq[MX + mxn], par[mxn][19];
vector<ll> adj[mxn];
bitset<mxn> mark;
set<int> s[2 * MX];

inline ll tav(ll a, ll b) {
    ll res = 1;
    while(b > 0) {
        if(b & 1) res = res * a % md;
        a = a * a % md, b >>= 1;
    } return res;
}

inline ll chs(ll a, ll b) {
    if(a < 0 || b > a) return 0;
    return fact[a] * taq[b] % md * taq[a - b] % md;
}

inline void fun() {
    fact[0] = 1;
    for(int i = 1; i < MX + mxn; i++) {
        fact[i] = fact[i - 1] * i % md;
    } taq[MX + mxn - 1] = tav(fact[MX + mxn - 1], md - 2);
    for(int i = MX + mxn - 2; i > -1; i--) {
        taq[i] = taq[i + 1] * (i + 1) % md;
    } return;
}

void DFS(int v) {
    mark.set(v);
    st[v] = q++, subt[v] = 1;
    for(int i = 1; i < 19; i++) {
        par[v][i] = par[par[v][i - 1]][i - 1];
    } for(auto u : adj[v]) {
        if(!mark[u]) {
            par[u][0] = v;
            h[u] = h[v] + 1;
            DFS(u);
            subt[v] += subt[u];
        }
    } ft[v] = q;
    return;
}

inline int find_par(int v, int x) {
    for(int i = 18; i > -1; i--) {
        if(x & (1 << i)) {
            v = par[v][i];
            x -= (1 << i);
            if(x == 0) return v;
        }
    } return v;
}

struct segtree {

    int sz = 1;
    vector<pll> v;

    void init(ll n) {
        while(sz < n) sz <<= 1;
        v.assign(2 * sz, {0, 0});
        return;
    }
    void set(int i, pll p, int x, int lx, int rx) {
        if(rx - lx == 1) {
            v[x] = p;
            return;
        } int m = (lx + rx) >> 1;
        if(i < m) {
            set(i, p, 2 * x + 1, lx, m);
        } else {
            set(i, p, 2 * x + 2, m, rx);
        } v[x].first = v[2 * x + 1].first + v[2 * x + 2].first;
        v[x].second = v[2 * x + 1].second + v[2 * x + 2].second;
        return;
    }
    void set(int i, pll p) {
        set(i, p, 0, 0, sz);
        return;
    }
    pll ask(int l, int r, int x, int lx, int rx) {
        if(rx <= l || r <= lx) return {0, 0};
        if(l <= lx && rx <= r) {
            return v[x];
        } int m = (lx + rx) >> 1;
        pll a = ask(l, r, 2 * x + 1, lx, m);
        pll b = ask(l, r, 2 * x + 2, m, rx);
        return {a.first + b.first, a.second + b.second};
    }
    pll ask(int l, int r) {
        return ask(l, r, 0, 0, sz);
    }

}; segtree stt;

struct fp {

    int sz = 1;
    
    void init(ll n) {
        while(sz < n) sz <<= 1;
        return;
    }
    void add(int l, int r, int q, int x, int lx, int rx) {
        if(rx <= l || r <= lx) return;
        if(l <= lx && rx <= r) {
            s[x].insert(-q);
            return;
        } int m = (lx + rx) >> 1;
        add(l, r, q, 2 * x + 1, lx, m);
        add(l, r, q, 2 * x + 2, m, rx);
        return;
    }
    void add(int l, int r, int q) {
        add(l, r, q, 0, 0, sz);
        return;
    }
    int ask(int i, int x, int lx, int rx) {
        int a = 0;
        if(int(s[x].size()) > 0) {
            a = *(s[x].begin()), a = -a;
        }
        if(rx - lx == 1) {
            if(int(s[x].size()) == 0) return 0;
            return -1 * (*(s[x].begin()));
        } int m = (lx + rx) >> 1;
        if(i < m) {
            return max(a, ask(i, 2 * x + 1, lx, m));
        } else {
            return max(a, ask(i, 2 * x + 2, m, rx));
        }
    }
    int ask(int i) {
        return ask(i, 0, 0, sz);
    }
    void rem(int l, int r, int q, int x, int lx, int rx) {
        if(rx <= l || r <= lx) return;
        if(l <= lx && rx <= r) {
            s[x].erase(-q);
            return;
        } int m = (lx + rx) >> 1;
        rem(l, r, q, 2 * x + 1, lx, m);
        rem(l, r, q, 2 * x + 2, m, rx);
        return;
    }
    void rem(int l, int r, int q) {
        rem(l, r, q, 0, 0, sz);
        return;
    }

}; fp fpar;

inline void input() {

    cin >> n >> r;
    for(int i = 1; i < n; i++) {
        cin >> q >> w;
        adj[q].push_back(w);
        adj[w].push_back(q);
    } cin >> t;

}

inline void solve() {

    fun(); q = 0;
    DFS(1);
    fill(dp, dp + mxn, 1);
    dp[1] = pw = chs(r + n - 1, n - 1);
    cout << pw << "\n";
    stt.init(n), fpar.init(n);
    fpar.add(1, n, 0); R[1] = r;
    for(int tt = 0; tt < t; tt++) {
        cin >> q;
        if(q == 1) {
            cin >> q >> w;
            R[q] = w;
            ll v = fpar.ask(st[q]), x, rp, sp;
            pll p;
            v = find_par(q, h[q] - v);
            if(dp[v] == 0) cnt--;
            else pw = pw * tav(dp[v], md - 2) % md;
            p = stt.ask(st[q] + 1, ft[q]);
            rp = R[q] - p.first, sp = subt[q] - p.second;
            x = chs(rp + sp - 1, sp - 1);
            if(x == 0) cnt++, dp[q] = 0;
            else {
                dp[q] = x, pw = pw * x % md;
            } stt.set(st[q], {rp, sp});
            fpar.add(st[q] + 1, ft[q], h[q]);
            p = stt.ask(st[v] + 1, ft[v]);
            rp = R[v] - p.first, sp = subt[v] - p.second;
            x = chs(rp + sp - 1, sp - 1);
            if(x == 0) cnt++, dp[v] = 0;
            else {
                dp[v] = x, pw = pw * x % md;
            } stt.set(st[v], {rp, sp});
            if(cnt == 0) {
                cout << pw << "\n";
            } else {
                cout << "0\n";
            }
            continue;
        } cin >> q;
        ll v = fpar.ask(st[q]), x, rp, sp;
        pll p;
        v = find_par(q, h[q] - v);
        if(dp[q] == 0) {
            cnt--, dp[q] = 1;
        } else {
            pw = pw * tav(dp[q], md - 2) % md, dp[q] = 1;
        } R[q] = 0;
        stt.set(st[q], {0, 0});
        fpar.rem(st[q] + 1, ft[q], h[q]);
        if(dp[v] == 0) {
            cnt--;
        } else {
            pw = pw * tav(dp[v], md - 2) % md;
        } 
        p = stt.ask(st[v] + 1, ft[v]);
        rp = R[v] - p.first, sp = subt[v] - p.second;
        x = chs(rp + sp - 1, sp - 1);
        if(x == 0) {
            cnt++, dp[v] = 0;
        } else {
            dp[v] = x, pw = pw * x % md;
        } stt.set(st[v], {rp, sp});
        if(cnt == 0) {
            cout << pw << "\n";
        } else {
            cout << "0\n";
        }
    }
    return;

}

int main() {

    ios::sync_with_stdio(false); cin.tie(NULL);

    input(), solve();

    return 0;

}

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