Submission #1365353

#TimeUsernameProblemLanguageResultExecution timeMemory
1365353HasanV11010238Sumtree (INOI20_sumtree)C++20
10 / 100
600 ms45004 KiB
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAX 600000
#define INF 1000000000000000000
#define mod 1000000007
ll binpow(ll a, ll b){
    ll res = 1;
    while (b != 0){
        if (b % 2 == 1){
            res *= a;
            res %= mod;
        }
        a *= a;
        a %= mod;
        b /= 2;
    }
    return res;
}
int n;
vector<vector<int>> v;
vector<ll> pa, emp, nee, us, st, en;
vector<ll> f, inv;
ll C(int n, int k){
    if (k > n || n < 0 || k < 0) return 0;
    return f[n] * inv[k] % mod * inv[n - k] % mod;
}
int nxt = 1;
void dfs(int x, int p){
    pa[x] = p;
    emp[x] = 1;
    st[x] = nxt;
    nxt++;
    for (auto el : v[x]){
        if (el != p){
            dfs(el, x);
            emp[x] += emp[el];
        }
    }
    en[x] = nxt;
}
vector<ll> tr;
void update(int v, int l, int r, int pos, ll val, int ty){
    if (l == r){
        if (ty == 0) tr[v] = val;
        else tr[v] += val;
        return;
    }
    int mid = (l + r) / 2;
    if (pos <= mid){
        update(v * 2, l, mid, pos, val, ty);
    }
    else{
        update(v * 2 + 1, mid + 1, r, pos, val, ty);
    }
    tr[v] = tr[v * 2] + tr[v * 2 + 1];
}
ll query(int v, int l, int r, int ql, int qr){
    if (l > qr || r < ql || ql > qr) return 0;
    if (ql <= l && r <= qr) return tr[v];
    int mid = (l + r) / 2;
    return query(v * 2, l, mid, ql, qr) + query(v * 2 + 1, mid + 1, r, ql, qr);
}
ll ans = 1, cnt0 = 0;
vector<int> isz;
void calcp(int x){
    if (us[x] == -1) return;
    int hm = us[x] - query(1, 1, n, st[x] + 1, en[x]);
    if (hm < 0 && isz[x] == 0) cnt0++, isz[x] = 1;
    else ans = (ans * C(emp[x] + hm - 1, emp[x] - 1)) % mod;
}
void calcm(int x){
    if (us[x] == -1) return;
    int hm = us[x] - query(1, 1, n, st[x] + 1, en[x]);
    if (hm < 0 && isz[x] == 1) cnt0--, isz[x] = 0;
    else ans = (ans * binpow(C(emp[x] + hm - 1, emp[x] - 1), mod - 2)) % mod;
}
void add(int x, int val){
    int hm = emp[x];
    calcm(x);
    us[x] = val;
    calcp(x);
    int wh = x;
    x = pa[x];
    while (us[x] == -1){
        emp[x] -= hm;
        x = pa[x];
    }
    calcm(x);
    int ne = us[wh] - query(1, 1, n, st[wh] + 1, en[wh]);
    update(1, 1, n, st[wh], ne, 0);
    update(1, 1, n, st[x], -ne, 1);
    emp[x] -= hm;
    calcp(x);
}
void del(int x){
    int val = us[x];
    calcm(x);
    us[x] = -1;
    calcm(x);
    int wh = x;
    x = pa[x];
    while (us[x] == -1){
        emp[x] += emp[wh];
        x = pa[x];
    }
    calcm(x);
    int ne = val - query(1, 1, n, st[wh] + 1, en[wh]);
    update(1, 1, n, st[wh], 0, 0);
    update(1, 1, n, st[x], ne, 1);
    emp[x] += emp[wh];
    calcp(x);
}
int main(){
    f.assign(MAX + 1, 1), inv.assign(MAX + 1, 1);
    for (ll i = 2; i <= MAX; i++){
        f[i] = (f[i - 1] * i) % mod;
        inv[i] = binpow(f[i], mod - 2);
    }
    int q, r, a, b;
    cin>>n>>r;
    v.assign(n + 1, vector<int>()), pa.assign(n + 1, 0), emp.assign(n + 1, 0), nee.assign(n + 1, 0);
    us.assign(n + 1, -1), st.assign(n + 1, 0), en.assign(n + 1, 0), isz.assign(n + 1, 0);
    for (int i = 0; i < n - 1; i++){
        cin>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    dfs(1, 0);
    cin>>q;
    nee[1] = r, us[1] = r;
    ans = C(n + r - 1, n - 1);
    tr.assign(4 * n + 4, 0);
    update(1, 1, n, 1, r, 0);
    cout<<ans<<"\n";
    for (int i = 1; i <= q; i++){
        cin>>a;
        if (a == 1){
            cin>>a>>b;
            add(a, b);
        }
        else{
            cin>>a;
            del(a);
        }
        if (cnt0 > 0) cout<<0<<"\n";
        else cout<<ans<<"\n";
    }
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...