Submission #1122196

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122196		Hamed_Ghaffari	Sumtree (INOI20_sumtree)	C++17	100 / 100	543 ms	160332 KiB

Main

#include <bits/stdc++.h>
using namespace std;

using ll  = long long;
using ld  = long double;
using pii = pair<int, int>;
using pll = pair<long long, long long>;
using ull = unsigned long long;

#define X               first
#define Y               second
#define SZ(x)           int(x.size())
#define all(x)          x.begin(), x.end()
#define mins(a,b)       (a = min(a,b))
#define maxs(a,b)       (a = max(a,b))
#define pb              push_back
#define Mp              make_pair
#define lc              id<<1
#define rc              lc|1
#define mid             ((l+r)/2)
mt19937_64              rng(chrono::steady_clock::now().time_since_epoch().count());

const ll  INF = 1e9 + 23;
const ll  MOD = 1e9 + 7;
const int MXN = 2e5 + 5;
const int MXR = 5e5 + 5;
const int LOG = 23;

ll F[MXR], I[MXR];
ll C(int n, int r) {
    return r<0||r>n ? 0 : F[n]*I[r]%MOD*I[n-r]%MOD;
}
ll IC(int n, int r) {
    return F[r]*F[n-r]%MOD*I[n]%MOD;
}

int n, q, par[MXN], stt[MXN], fnt[MXN], timer, ver[MXN], fen[2][MXN], label[MXN];
int c0;
ll ans;
vector<int> g[MXN];

void dfs(int v) {
    ver[stt[v] = ++timer] = v;
    for(int u : g[v])
        if(u^par[v])
            par[u] = v,
            dfs(u);
    fnt[v] = timer;
}

void updx(int ind, int p, int x) {
    for(p+=2; p<MXN; p+=p&-p) fen[ind][p] += x;
}
int getx(int ind, int p) {
    int res=0;
    for(p+=2; p; p-=p&-p) res += fen[ind][p];
    return res;
}
int getr(int ind, int s, int e) {
    return getx(ind, e) - getx(ind, s-1);
}

void add(int v) {
    int sz = getr(0, stt[v], fnt[v]);
    int R = label[v] - getr(1, stt[v], fnt[v]);
    if(C(R+sz-1, sz-1)) (ans *= C(R+sz-1, sz-1)) %= MOD;
    else c0++;
}

void rem(int v) {
    int sz = getr(0, stt[v], fnt[v]);
    int R = label[v] - getr(1, stt[v], fnt[v]);
    if(C(R+sz-1, sz-1)) (ans *= IC(R+sz-1, sz-1)) %= MOD;
    else c0--;
}

set<int> seg[MXN<<2];
void insert(int s, int e, int x, int l=1, int r=n+1, int id=1) {
    if(s<=l && r<=e) {
        seg[id].insert(x);
        return;
    }
    if(s<mid) insert(s,e,x, l, mid, lc);
    if(e>mid) insert(s,e,x, mid, r, rc);
}
void erase(int s, int e, int x, int l=1, int r=n+1, int id=1) {
    if(s<=l && r<=e) {
        seg[id].erase(x);
        return;
    }
    if(s<mid) erase(s,e,x, l, mid, lc);
    if(e>mid) erase(s,e,x, mid, r, rc);
}
int get_par(int p, int l=1, int r=n+1, int id=1) {
    int res = (seg[id].empty() ? 0 : *seg[id].rbegin());
    if(r-l > 1) {
        if(p<mid) maxs(res, get_par(p, l, mid, lc));
        else maxs(res, get_par(p, mid, r, rc));
    }
    return res;
}

#define ANS (c0 ? 0 : ans)

void Main() {
    F[0] = 1;
    for(int i=1; i<MXR; i++) F[i] = F[i-1]*i%MOD;
    I[0] = I[1] = 1;
    for(int i=2; i<MXR; i++) I[i] = (MOD-MOD/i)*I[MOD%i]%MOD;
    for(int i=2; i<MXR; i++) (I[i] *= I[i-1]) %= MOD;
    cin >> n >> label[1];
    for(int i=1, u,v; i<n; i++) {
        cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }
    dfs(1);
    for(int i=1; i<=n; i++) updx(0, stt[i], 1);
    insert(1, n+1, 1);
    ans = 1;
    add(1);
    cout << ANS << '\n';
    cin >> q;
    while(q--) {
        int t;
        cin >> t;
        if(t == 1) {
            int v;
            cin >> v;
            cin >> label[v];
            int u = ver[get_par(stt[v])];
            insert(stt[v], fnt[v]+1, stt[v]);
            rem(u);
            add(v);
            int sz = getr(0, stt[v], fnt[v]);
            int R = label[v] - getr(1, stt[v], fnt[v]);
            updx(0, stt[par[v]], -sz);
            if(par[u]) updx(0, stt[par[u]], sz);
            updx(1, stt[par[v]], R);
            if(par[u]) updx(1, stt[par[u]], -R);
            add(u);
        }
        else {
            int v;
            cin >> v;
            erase(stt[v], fnt[v]+1, stt[v]);
            int u = ver[get_par(stt[v])];
            rem(v);
            rem(u);
            int sz = getr(0, stt[v], fnt[v]);
            int R = label[v] - getr(1, stt[v], fnt[v]);
            updx(0, stt[par[v]], sz);
            if(par[u]) updx(0, stt[par[u]], -sz);
            updx(1, stt[par[v]], -R);
            if(par[u]) updx(1, stt[par[u]], R);
            add(u);
        }
        cout << ANS << '\n';
    }
}

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    int T = 1;
    // cin >> T;
    while(T--) Main();
    return 0;
}

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