oj.uz

Submission #635592

# Submission time Handle Problem Language Result Execution time Memory
635592 2022-08-26T13:33:56 Z MohammadAghil Sumtree (INOI20_sumtree) C++17
10 / 100
 463 ms 110776 KB 
#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 = 5e5 + 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[i] = pw(fac[i], mod-2);
    }
 
    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 par[r][0];
    };
 
    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;
        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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 251 ms 60604 KB Output is correct
2 Correct 279 ms 60772 KB Output is correct
3 Correct 262 ms 60620 KB Output is correct
4 Correct 256 ms 60628 KB Output is correct
5 Correct 230 ms 56652 KB Output is correct
6 Correct 116 ms 20612 KB Output is correct
7 Correct 105 ms 20300 KB Output is correct
8 Correct 108 ms 20396 KB Output is correct
9 Correct 276 ms 52996 KB Output is correct
10 Correct 249 ms 52768 KB Output is correct
11 Correct 273 ms 53000 KB Output is correct
12 Correct 247 ms 51276 KB Output is correct
13 Correct 224 ms 57332 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 105 ms 19820 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 284 ms 61376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 463 ms 110776 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 251 ms 60604 KB Output is correct
2 Correct 279 ms 60772 KB Output is correct
3 Correct 262 ms 60620 KB Output is correct
4 Correct 256 ms 60628 KB Output is correct
5 Correct 230 ms 56652 KB Output is correct
6 Correct 116 ms 20612 KB Output is correct
7 Correct 105 ms 20300 KB Output is correct
8 Correct 108 ms 20396 KB Output is correct
9 Correct 276 ms 52996 KB Output is correct
10 Correct 249 ms 52768 KB Output is correct
11 Correct 273 ms 53000 KB Output is correct
12 Correct 247 ms 51276 KB Output is correct
13 Correct 224 ms 57332 KB Output is correct
14 Incorrect 105 ms 19820 KB Output isn't correct
15 Halted 0 ms 0 KB -