Submission #635630

#	Time	Username	Problem	Language	Result	Execution time	Memory
635630		MohammadAghil	Sumtree (INOI20_sumtree)	C++17	100 / 100	564 ms	92932 KiB

Main

#include <bits/stdc++.h>
//#pragma GCC optimize ("Ofast,unroll-loops")
//#pragma GCC target ("avx2")
using namespace std;

typedef long long ll;
typedef pair<int, int> pp;

#define rep(i,l,r) for(int i = (l); i < (r); i++)
#define per(i,r,l) for(int i = (r); i >= (l); i--)
#define all(x) begin(x), end(x)
#define sz(x) (int)x.size()
#define pb push_back
#define ff first
#define ss second

void dbg(){
    cerr << endl;
}
template<typename Head, typename... Tail> void dbg(Head h, Tail... t){
    cerr << " " << h << ",";
    dbg(t...);
}
#define er(...) cerr << __LINE__ << " <" << #__VA_ARGS__ << ">:", dbg(__VA_ARGS__)

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

void IOS(){
    cin.tie(0) -> sync_with_stdio(0);
//    #ifndef ONLINE_JUDGE
//        freopen("inp.txt", "r", stdin);
//        freopen("out.txt", "w", stdout);
//    #endif
}

const ll mod = 1e9 + 7, maxn = 1e6 + 5, lg = 21, inf = ll(1e9) + 5;

struct SegMul{
    vector<ll> seg;
    int n;
    SegMul(int n): n(n){
        seg.assign(n<<1, 1);
    }
    void upd(int i, ll k){
        for(i += n, seg[i] = k; i > 1; i >>= 1) seg[i>>1] = seg[i]*seg[i^1]%mod;
    }
    ll get(){
        return seg[1];
    }
};

struct Fen{
    vector<ll> fen;
    Fen(int n){
        fen.assign(n + 5, 0);
    }
    void upd(int i, ll k){
        for(i++; i < sz(fen); i += i&-i) fen[i] += k;
    }
    ll get(int i){
        ll res = 0;
        for(i++; i; i -= i&-i) res += fen[i];
        return res;
    }
    ll get(int l, int r){
        return get(r - 1) - get(l - 1);
    }
};

ll pw(ll a, ll b){
    if(!b) return 1;
    ll k = pw(a, b>>1ll);
    return  k*k%mod*(b&1ll?a:1ll)%mod;
}

ll fac[maxn], inv[maxn];

ll C(int n, int r){
    if(r < 0 || r > n) return 0;
    return fac[n]*inv[r]%mod*inv[n-r]%mod;
}

vector<int> adj[maxn];
int st[maxn], en[maxn],  par[maxn][lg], t, cnt[maxn];
ll val[maxn];

void dfs(int r, int p){
    cnt[r] = 1;
    st[r] = t++;
    par[r][0] = p;
    rep(i,1,lg) par[r][i] = par[par[r][i-1]][i-1];
    for(int c: adj[r]) if(c - p){
        dfs(c, r);
        cnt[r] += cnt[c];
    }
    en[r] = t;
}

int main(){ IOS();
    fac[0] = inv[0] = 1;

    rep(i,1,maxn){
        fac[i] = fac[i-1]*i%mod;
    }
    inv[maxn-1] = pw(fac[maxn-1], mod-2);
    per(i,maxn-2,0) inv[i] = inv[i + 1]*(i + 1)%mod;

    int n, r; cin >> n >> r;
    val[0] = r;

    rep(i,1,n){
        int u, v; cin >> u >> v; u--, v--;
        adj[u].pb(v), adj[v].pb(u);
    }
    dfs(0, 0);

    SegMul smul(n); smul.upd(0, C(r + n - 1, r));
    Fen fen_par(n); fen_par.upd(st[0], 1), fen_par.upd(en[0], -1);
    Fen cnt_sub(n); cnt_sub.upd(0, n);
    Fen sum_val(n); sum_val.upd(0, r);

    auto get_par = [&](int r){
        int vl = fen_par.get(st[r]);
        per(i,lg-1,0){
            int p = par[r][i];
            if(vl == fen_par.get(st[p])) r = p;
        }
        return r;
    };

    auto add = [&](int r, int x){
        int p = get_par(r);
        fen_par.upd(st[r], 1), fen_par.upd(en[r], -1);
        ll fl = cnt_sub.get(st[r], en[r]);
        ll emp = cnt[r] - fl;
//        er(r, x, p, emp);
        cnt_sub.upd(st[r], emp);
        cnt_sub.upd(st[p], -emp);
        sum_val.upd(st[r], val[r] = x - sum_val.get(st[r], en[r]));
        smul.upd(r, C(val[r] + emp - 1, val[r]));
        sum_val.upd(st[p], -val[r]); val[p] -= val[r];
        emp = cnt_sub.get(st[p], st[p] + 1);
        smul.upd(p, C(val[p] + emp - 1, val[p]));
    };

    auto rem = [&](int r){
        fen_par.upd(st[r], -1), fen_par.upd(en[r], 1);
        int p = get_par(r);
        int tmp;
        cnt_sub.upd(st[r], tmp = -cnt_sub.get(st[r], st[r] + 1));
        cnt_sub.upd(st[p], -tmp);
        sum_val.upd(st[r], -val[r]);
        smul.upd(r, 1);
        sum_val.upd(st[p], val[r]); val[p] += val[r], val[r] = 0;
        int emp = cnt_sub.get(st[p], st[p] + 1);
        smul.upd(p, C(val[p] + emp - 1, val[p]));
    };

    int q; cin >> q;
    cout << smul.get() << '\n';
    while(q--){
        int t; cin >> t;
        if(t == 1){
            int u, x; cin >> u >> x; u--;
            add(u, x);
        }else{
            int u; cin >> u; u--;
            rem(u);
        }
        cout << smul.get() << '\n';
    }

    return 0;
}

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