oj.uz

Submission #635580

# Submission time Handle Problem Language Result Execution time Memory
635580 2022-08-26T13:20:43 Z MohammadAghil Sumtree (INOI20_sumtree) C++17
10 / 100
 458 ms 111280 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 257 ms 61456 KB Output is correct
2 Correct 251 ms 61188 KB Output is correct
3 Correct 261 ms 61304 KB Output is correct
4 Correct 257 ms 61188 KB Output is correct
5 Correct 227 ms 57164 KB Output is correct
6 Correct 109 ms 20768 KB Output is correct
7 Correct 109 ms 20388 KB Output is correct
8 Correct 107 ms 20436 KB Output is correct
9 Correct 256 ms 53452 KB Output is correct
10 Correct 263 ms 53324 KB Output is correct
11 Correct 250 ms 53496 KB Output is correct
12 Correct 253 ms 51852 KB Output is correct
13 Correct 243 ms 57896 KB Output is correct

Subtask #2
0 / 20.0

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

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 275 ms 62036 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 458 ms 111280 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 257 ms 61456 KB Output is correct
2 Correct 251 ms 61188 KB Output is correct
3 Correct 261 ms 61304 KB Output is correct
4 Correct 257 ms 61188 KB Output is correct
5 Correct 227 ms 57164 KB Output is correct
6 Correct 109 ms 20768 KB Output is correct
7 Correct 109 ms 20388 KB Output is correct
8 Correct 107 ms 20436 KB Output is correct
9 Correct 256 ms 53452 KB Output is correct
10 Correct 263 ms 53324 KB Output is correct
11 Correct 250 ms 53496 KB Output is correct
12 Correct 253 ms 51852 KB Output is correct
13 Correct 243 ms 57896 KB Output is correct
14 Incorrect 105 ms 19916 KB Output isn't correct
15 Halted 0 ms 0 KB -