oj.uz

Submission #789186

# Submission time Handle Problem Language Result Execution time Memory
789186 2023-07-21T07:14:28 Z MISM06 Sumtree (INOI20_sumtree) C++14
10 / 100
 206 ms 98756 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 = 5e5 + 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];
bool is[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] - 1);
			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]);

			int p = find_par(v);
			ct[p] -= ct[v];
			f1.upd(st[v], -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]);
			s[chp[v]].insert({-h[v], v});
			out();
		} else {
			int v; cin >> v;
			f1.upd(st[v], -ct[v]);
			f2.upd(st[v], -a[v]);
			// cout << "* " << rs[v] << '\n';
			if (rs[v] == 0) --c0;
			else ANS = mul(ANS, pw(rs[v], mod - 2));
			// cout << ANS << '\n';
			s[chp[v]].erase({-h[v], v});
			
			int p = find_par(v);
			// cout << "p = " << p << '\n';
			ct[p] += ct[v];
			a[p] += a[v];
			// cout << ct[p] << " , " << a[p] << " , " << rs[p] << '\n';
			if (rs[p] == 0) --c0;
			else ANS = mul(ANS, pw(rs[p], mod - 2));
			// cout << ANS << '\n';
			rs[p] = choose(a[p] + ct[p] - 1, ct[p] - 1);
			if (rs[p] == 0) ++c0;
			else ANS = mul(ANS, rs[p]);
			// cout << ANS << '\n';
			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 105 ms 54380 KB Output is correct
2 Correct 127 ms 54448 KB Output is correct
3 Correct 131 ms 54452 KB Output is correct
4 Correct 113 ms 54408 KB Output is correct
5 Correct 103 ms 50584 KB Output is correct
6 Correct 20 ms 27440 KB Output is correct
7 Correct 16 ms 27164 KB Output is correct
8 Correct 18 ms 27220 KB Output is correct
9 Correct 115 ms 46760 KB Output is correct
10 Correct 120 ms 46656 KB Output is correct
11 Correct 107 ms 46708 KB Output is correct
12 Correct 114 ms 45760 KB Output is correct
13 Correct 114 ms 52452 KB Output is correct

Subtask #2
0 / 20.0

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

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 124 ms 57216 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 206 ms 98756 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 105 ms 54380 KB Output is correct
2 Correct 127 ms 54448 KB Output is correct
3 Correct 131 ms 54452 KB Output is correct
4 Correct 113 ms 54408 KB Output is correct
5 Correct 103 ms 50584 KB Output is correct
6 Correct 20 ms 27440 KB Output is correct
7 Correct 16 ms 27164 KB Output is correct
8 Correct 18 ms 27220 KB Output is correct
9 Correct 115 ms 46760 KB Output is correct
10 Correct 120 ms 46656 KB Output is correct
11 Correct 107 ms 46708 KB Output is correct
12 Correct 114 ms 45760 KB Output is correct
13 Correct 114 ms 52452 KB Output is correct
14 Incorrect 17 ms 26900 KB Output isn't correct
15 Halted 0 ms 0 KB -