Submission #627090

#	Time	Username	Problem	Language	Result	Execution time	Memory
627090		AA_Surely	Sumtree (INOI20_sumtree)	C++14	10 / 100	189 ms	40608 KiB

Main

#include <bits/stdc++.h>

#define FOR(i, x, n) for(int i = x; i < n; i++)
#define F0R(i, n) FOR(i, 0, n)
#define ROF(i, x, n) for(int i = n - 1; i >= x; i--)
#define R0F(i, n) ROF(i, 0, n)

#define WTF cout << "WTF" << endl

#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define F first
#define S second
#define PB push_back

#define ALL(x) x.begin(), x.end()
#define RALL(x) x.rbegin(), x.rend()

using namespace std;

typedef long long LL;

typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

typedef vector<int> VI;
typedef vector<LL> VLL;
typedef vector<PII> VPII;
typedef vector<PLL> VPLL;

const int N = 5e5 + 7;
const int LOG = 22;
const int INF = 1e9 + 7;
const int MOD = 1e9 + 7;

#define endl '\n'

LL fact[N], ifact[N];
LL chs[N], ans, val[N];
bool active[N];
int ns[N], n, q, bad, par[N], sz[N];
VI adj[N];

inline int pw(LL a, int b) {
    LL ret = 1;
    for(; b; b >>= 1, a = a * a % MOD)
        if (b & 1) ret = ret *a % MOD;
    return ret;
}

void precalc() {
    fact[0] = 1;
    FOR(i, 1, N) fact[i] = fact[i - 1] * i % MOD;
    ifact[N - 1] = pw(fact[N - 1], MOD - 2);
    R0F(i, N - 1) ifact[i] = ifact[i + 1] * (i + 1) % MOD;
    return;
}

inline int nCr(int nn, int rr) {
    if (nn < rr || rr < 0) return 0;
    return (fact[nn] * ifact[rr] % MOD) * ifact[nn - rr] % MOD;
}

void init() {
    cin >> n >> ns[0];
    F0R(i, n - 1) {
        int u, v;
        cin >> u >> v;
        adj[--u].PB(--v);
        adj[v].PB(u);
    }

    cin >> q;
    return;
}

void dfs(int now, int p) {
    par[now] = p;
    sz[now] = 1;
    for(int on : adj[now]) if (on != p) {
        dfs(on, now);
        sz[now] += sz[on];
    }
    return;
}

void updChoose(int now) {
    if (!chs[now]) bad--;
    else ans = (ans * pw(chs[now], MOD - 2)) % MOD;

    chs[now] = nCr(val[now] + sz[now] - 1, sz[now] - 1);

    if (!chs[now]) bad++;
    else ans = (ans * chs[now]) % MOD;

    return;
}

void addTag() {
    int v, x;
    cin >> v >> x;
    v--;
    val[v] = x;
    
    int now = par[v];
    while(!active[now]) {
        sz[now] -= sz[v];
        now = par[now];
    }

    sz[now] -= sz[v];
    val[now] -= x;

    updChoose(now);
    updChoose(v);

    active[v] = 1;
    return;
}

int main() {
    IOS;

    init();
    precalc();
    dfs(0, -1);

    active[0] = 1;
    fill(chs, chs + n, 1);
    chs[0] = nCr(ns[0] + n - 1, n - 1);
    ans = chs[0];
    val[0] = ns[0];

    cout << ans << endl;

    while(q--) {
        int tp; cin >> tp;
        if (tp == 1) addTag();
        //else remTag();

        cout << (bad ? 0 : ans) << endl;
    }
}

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