oj.uz

답안 #635528

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
635528 2022-08-26T11:16:58 Z MohammadAghil Sumtree (INOI20_sumtree) C++17
10 / 100
 464 ms 110812 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 + 1, 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);
//        er(r, p);
        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);
//        er(emp, val[p], C(val[p] + emp - 1, emp));
        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

# 결과 실행 시간 메모리 Grader output
1 Correct 278 ms 60740 KB Output is correct
2 Correct 261 ms 60624 KB Output is correct
3 Correct 260 ms 60684 KB Output is correct
4 Correct 256 ms 60604 KB Output is correct
5 Correct 228 ms 56620 KB Output is correct
6 Correct 108 ms 20548 KB Output is correct
7 Correct 107 ms 20428 KB Output is correct
8 Correct 106 ms 20408 KB Output is correct
9 Correct 262 ms 53000 KB Output is correct
10 Correct 261 ms 52952 KB Output is correct
11 Correct 250 ms 52964 KB Output is correct
12 Correct 253 ms 51348 KB Output is correct
13 Correct 249 ms 57268 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 109 ms 19912 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 265 ms 61520 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 464 ms 110812 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 278 ms 60740 KB Output is correct
2 Correct 261 ms 60624 KB Output is correct
3 Correct 260 ms 60684 KB Output is correct
4 Correct 256 ms 60604 KB Output is correct
5 Correct 228 ms 56620 KB Output is correct
6 Correct 108 ms 20548 KB Output is correct
7 Correct 107 ms 20428 KB Output is correct
8 Correct 106 ms 20408 KB Output is correct
9 Correct 262 ms 53000 KB Output is correct
10 Correct 261 ms 52952 KB Output is correct
11 Correct 250 ms 52964 KB Output is correct
12 Correct 253 ms 51348 KB Output is correct
13 Correct 249 ms 57268 KB Output is correct
14 Incorrect 109 ms 19912 KB Output isn't correct
15 Halted 0 ms 0 KB -