Submission #1242234

#TimeUsernameProblemLanguageResultExecution timeMemory
1242234BahaminSumtree (INOI20_sumtree)C++20
50 / 100
3096 ms41440 KiB
#include <bits/stdc++.h> using namespace std; #pragma GCC target("sse4") #pragma GCC optimize("07") #pragma GCC optimize ("unroll-loops") template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; } template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; } #define ll long long #define ld long double #define all(a) (a).begin(), (a).end() #define sui cout.tie(NULL); cin.tie(NULL); ios_base::sync_with_stdio(false) #define lid id << 1 #define rid id << 1 | 1 #define mid ((r + l) >> 1) const int MAX_N = 3e5 + 1; const int MOD = 1e9 + 7; const ll INF = 1e9; const ld EPS = 1e-9; const int LOG = 30; const int h = MAX_N, w = MAX_N; vector<ll> inv(h+w+1); vector<ll> fact(h+w+1); vector<ll> fact_inv(h+w+1); inline int md(ll x) {x %= MOD; return x + (x < 0 ? MOD : 0);} inline int ADD(ll a, ll b) { return md(a+b); } inline int SUB(ll a, ll b) { return md(a-b); } inline int MUL(ll a, ll b) { return md(1ll*a*b); } inline int POW(ll a, ll b) { int res=1;while(b){if(b&1)res=MUL(res,a);a=MUL(a,a);b>>=1;}return res; } inline int DIV(ll a, ll b) { return MUL(a, POW(b, MOD-2)); } inline int comb(ll n, ll k){ if (n<0 || k<0) return 0LL; if (n < k) return 0LL; return fact[n] * fact_inv[n - k] % MOD * fact_inv[k] % MOD; }; void init() { inv[1] = 1; for(int i=2; i<h+w+1; i++){ inv[i] = MOD - (MOD/i) * inv[MOD%i] % MOD; } fact[0] = 1; fact_inv[0] = 1; for(int i=1; i<h+w+1; i++){ fact[i] = fact[i-1] * i % MOD; fact_inv[i] = fact_inv[i-1] * inv[i] % MOD; } } int st[MAX_N]; int fi[MAX_N]; int rev[MAX_N]; int sz[MAX_N]; int timer = 0; vector<int> adj[MAX_N]; int have[MAX_N]; int seg2[MAX_N]; int mul = 1; int zero = 0; int n, rr; void dfs(int u, int p) { st[u] = timer++; rev[st[u]] = u; sz[u] = 1; for (int v : adj[u]) if (v != p) dfs(v, u), sz[u] += sz[v]; fi[u] = timer; } int seg1[MAX_N << 2]; void upd1(int x, bool y, int l, int r, int id) { if (l == r - 1) { if (y) seg1[id] = fi[rev[l]]; else seg1[id] = 0; return; } if (x < mid) upd1(x, y, l, mid, lid); else upd1(x, y, mid, r, rid); seg1[id] = max(seg1[lid], seg1[rid]); } int get1(int s, int t, int x, int l, int r, int id) { if (s >= r || t <= l || seg1[id] <= x) return -INF; if (l == r - 1) return l; return max(get1(s, t, x, l, mid, lid), get1(s, t, x, mid, r, rid)); } inline int getpar(int u) { return rev[get1(0, st[u], st[u], 0, n, 1)]; } inline void upd2(int x, int y, int l, int r, int id) { if (seg2[x] == 0) zero--; if (y == 0) zero++; if (seg2[x]) mul = DIV(mul, seg2[x]); if (y) mul = MUL(mul, y); seg2[x] = y; } pair<ll, ll> fen[MAX_N]; inline void upd3(int x, ll y, ll z) { x++; for (int i = x; i < MAX_N; i += i & (-i)) fen[i].first += y, fen[i].second += z; } inline pair<ll, ll> get3(int x) { x++; pair<ll, ll> re; for (int i = x; i > 0; i -= i & (-i)) re.first += fen[i].first, re.second += fen[i].second; return re; } inline pair<ll, ll> get3(int l, int r) { pair<ll, ll> x = get3(r - 1); pair<ll, ll> y = get3(l - 1); return make_pair(x.first - y.first, x.second - y.second); } inline void calc(int u) { auto ge = get3(st[u] + 1, fi[u]); ll x = have[u] - ge.second; ll y = sz[u] - ge.first; upd2(st[u], comb(x + y - 1, y - 1), 0, n, 1); } inline void add(int u, int x) { have[u] = x; int p = getpar(u); auto xx = get3(st[u] + 1, fi[u]); upd3(st[u], sz[u] - xx.first, have[u] - xx.second); upd3(st[p], xx.first - sz[u], xx.second - have[u]); calc(u), 0; calc(p), 0; upd1(st[u], true, 0, n, 1); } inline void rem(int u) { int p = getpar(u); auto xx = get3(st[u] + 1, fi[u]); upd3(st[u], xx.first - sz[u], xx.second - have[u]); upd3(st[p], -xx.first + sz[u], -xx.second + have[u]); have[u] = -1; upd2(st[u], 1, 0, n, 1); calc(p); upd1(st[u], false, 0, n, 1); } void solve() { init(); cin >> n >> rr; for (int i = 1; i < n; i++) { int u, v; cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); } fill(seg2, seg2 + n, 1); fill(have, have + n + 1, -1); dfs(1, 0); have[1] = rr; upd3(st[1], sz[1], rr); upd1(st[1], true, 0, n, 1); calc(1); cout << (zero ? 0 : mul) << "\n"; int q; cin >> q; while (q--) { int c; cin >> c; if (c == 1) { int v, x; cin >> v >> x; add(v, x); } else { int v; cin >> v; rem(v); } cout << (zero ? 0 : mul) << "\n"; } } int main() { sui; int tc = 1; //cin >> tc; for (int t = 1; t <= tc; t++) { solve(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...