oj.uz

Submission #789211

# Submission time Handle Problem Language Result Execution time Memory
789211 2023-07-21T07:51:16 Z MISM06 Sumtree (INOI20_sumtree) C++17
10 / 100
 293 ms 57616 KB 
//0 1 1 0 1
//0 1 0 0 1
//1 0 0 1 1
//0 1 1 0 1
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
// #pragma GCC target("avx2")

using namespace std;

#define F 			first
#define S 			second
#define pb 			push_back
#define sze			size()
#define	all(x)		x.begin() , x.end()
#define wall__		cout << "--------------------------------------\n";
#define kids		int mid = (tl + tr) >> 1, cl = v << 1, cr = v << 1 | 1
#define file_io		freopen("input.cpp", "r", stdin); freopen("output.cpp", "w", stdout);

typedef long long ll;
typedef long double dl;
typedef pair < int , int > pii;
typedef pair < int , ll > pil;
typedef pair < ll , int > pli;
typedef pair < ll , ll > pll;
typedef pair < int , pii > piii;
typedef pair < ll, pll > plll;


const ll N = 2e5 + 10, M = 6e5 + 10;
const ll mod = 1e9 + 7;
const ll inf = 2e16;
const ll INF = 1e9 + 10;
const ll lg = 32;

ll fac[M], inv[M];
inline void add (ll &x, ll y) {
	x += y; if (x >= mod) x -= mod;
	if (x < 0) x += mod;
}
inline ll Sum (ll x, ll y) {
	x += y; if (x >= mod) x -= mod;
	if (x < 0) x += mod;
	return x;
}
inline ll mul (ll x, ll y) {
	x *= y; x %= mod; if (x < 0) x+= mod;
	return x;
}
inline ll pw (ll x, ll y) {
	ll res = 1;
	while(y) {
		if (y & 1) res = mul(res, x);
		x = mul(x, x);
		y >>= 1;
	}
	return res;
}
inline ll choose (ll x, ll y) {
	if (x < y || y < 0) return 0;
	return mul(fac[x], mul(inv[y], inv[x - y]));
}

ll n, chp[N], par[N], hv[N], h[N], sub[N], ANS;
ll a[N], st[N], en[N], timer = 0, ct[N], rs[N], c0;
set < pii > s[N];
vector < int > g[N];

struct fen {
	ll bit[N];
	fen () {
		fill(bit, bit + N, 0);
	}
	inline ll read (int idx) {
		ll res = 0;
		for (; idx > 0; idx -= (idx & -idx)) res += bit[idx];
		return res;
	}
	inline void upd (int idx, ll val) {
		for (; idx <= n; idx += (idx & -idx)) 
			bit[idx] += val;
	}
	inline ll range (int l, int r) {
		return read(r) - read(l - 1);
	}
} f1, f2;
void dfs0 (int v, int p) {
	par[v] = p;
	h[v] = h[p] + 1;
	st[v] = ++timer;
	sub[v] = 1;
	for (auto u : g[v]) {
		if (u == p) continue;
		dfs0(u, v);
		sub[v] += sub[u];
		if (sub[u] > sub[hv[v]]) hv[v] = u;
	}
	en[v] = timer;
}
void dfs (int v, int p) {
	for (auto u : g[v]) {
		if (u == p) continue;
		if (hv[v] == u) chp[u] = chp[v];
		else chp[u] = u;
		dfs(u, v);
	}
}
void out () {
	if (c0 > 0) cout << 0 << '\n';
	else cout << ANS << '\n';
}
int find_par (int v) {
	int p = chp[v];
	while (s[p].lower_bound({-h[v] + 1, 0}) == s[p].end()) {
		p = chp[par[p]];
	}
	pii x = *s[p].lower_bound(make_pair(-h[v] + 1, 0));
	return x.S;
}
void solve () {

	cin >> n >> a[1];
	for (int i = 1; i < n; i++) {
		int v, u; cin >> v >> u;
		g[v].pb(u); g[u].pb(v);
	}
	chp[1] = 1;
	dfs0(1, 0);
	dfs(1, 0);
	ct[1] = n; f1.upd(st[1], n); f2.upd(st[1], a[1]);
	fill(rs, rs + N, -1);
	rs[1] = choose(a[1] + ct[1] - 1, ct[1] - 1);
	ANS = rs[1];
	s[chp[1]].insert({-h[1], 1});
	out();
	int q; cin >> q;
	while (q--) {
		int t; cin >> t;
		if (t == 1) {
			int v, x; cin >> v >> x;
			ct[v] = sub[v] - f1.range(st[v], en[v]);
			f1.upd(st[v], ct[v]);
			a[v] = x - f2.range(st[v], en[v]);
			f2.upd(st[v], a[v]);
			rs[v] = choose(a[v] + ct[v] - 1, ct[v] - 1);
			if (rs[v] == 0) ++c0;
			else ANS = mul(ANS, rs[v]);
			s[chp[v]].insert({-h[v], v});

			int p = find_par(v);
			ct[p] -= ct[v];
			f1.upd(st[p], -ct[v]);
			a[p] -= a[v];
			f2.upd(st[p], -a[v]);
			if (rs[p] == 0) --c0;
			else ANS = mul(ANS, pw(rs[p], mod - 2));
			rs[p] = choose(a[p] + ct[p] - 1, ct[p] - 1);
			if (rs[p] == 0) ++c0;
			else ANS = mul(ANS, rs[p]);
			out();
		} else {
			int v; cin >> v;
			f1.upd(st[v], -ct[v]);
			f2.upd(st[v], -a[v]);
			if (rs[v] == 0) --c0;
			else ANS = mul(ANS, pw(rs[v], mod - 2));
			s[chp[v]].erase({-h[v], v});
			
			int p = find_par(v);
			ct[p] += ct[v];
			f1.upd(st[p], ct[v]);
			a[p] += a[v];
			f2.upd(st[p], a[v]);
			if (rs[p] == 0) --c0;
			else ANS = mul(ANS, pw(rs[p], mod - 2));
			rs[p] = choose(a[p] + ct[p] - 1, ct[p] - 1);
			if (rs[p] == 0) ++c0;
			else ANS = mul(ANS, rs[p]);
			out();
		}
	}


}


int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	fac[0] = 1;
	for (int i = 1; i < M; i++) fac[i] = mul(fac[i - 1], i);
	inv[M - 1] = pw(fac[M - 1], mod - 2);
	for (int i = M - 2; i >= 0; --i) inv[i] = mul(inv[i + 1], i + 1);
	int t = 1;
	// cin >> t;
	while (t--) {solve();}
    return 0;
}
/*
*/
//shrek is love;

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 54092 KB Output is correct
2 Correct 109 ms 54100 KB Output is correct
3 Correct 127 ms 54096 KB Output is correct
4 Correct 130 ms 54084 KB Output is correct
5 Correct 102 ms 50052 KB Output is correct
6 Correct 20 ms 29020 KB Output is correct
7 Correct 18 ms 28756 KB Output is correct
8 Correct 18 ms 28888 KB Output is correct
9 Correct 131 ms 46396 KB Output is correct
10 Correct 128 ms 46412 KB Output is correct
11 Correct 133 ms 46452 KB Output is correct
12 Correct 106 ms 45516 KB Output is correct
13 Correct 98 ms 52348 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 28500 KB Output is correct
2 Incorrect 17 ms 28456 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 56848 KB Output is correct
2 Incorrect 191 ms 57616 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 54092 KB Output is correct
2 Correct 109 ms 54100 KB Output is correct
3 Correct 127 ms 54096 KB Output is correct
4 Correct 130 ms 54084 KB Output is correct
5 Correct 102 ms 50052 KB Output is correct
6 Correct 20 ms 29020 KB Output is correct
7 Correct 18 ms 28756 KB Output is correct
8 Correct 18 ms 28888 KB Output is correct
9 Correct 131 ms 46396 KB Output is correct
10 Correct 128 ms 46412 KB Output is correct
11 Correct 133 ms 46452 KB Output is correct
12 Correct 106 ms 45516 KB Output is correct
13 Correct 98 ms 52348 KB Output is correct
14 Correct 17 ms 28500 KB Output is correct
15 Incorrect 17 ms 28456 KB Output isn't correct
16 Halted 0 ms 0 KB -