oj.uz

Submission #789476

# Submission time Handle Problem Language Result Execution time Memory
789476 2023-07-21T12:32:35 Z MISM06 Sumtree (INOI20_sumtree) C++14
10 / 100
 307 ms 83772 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 = 5e5 + 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;
	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;
	}
}
void dfs (int v, int p) {
	st[v] = ++timer;
	if (hv[v] != 0) {
		chp[hv[v]] = chp[v];
		dfs(hv[v], v);
	}
	for (auto u : g[v]) {
		if (u == p || hv[v] == u) continue;
		chp[u] = u;
		dfs(u, v);
	}
	en[v] = timer;
}
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], 0}) == s[p].begin() || s[p].sze == 0) {
		p = chp[par[p]];
	}
	auto it = s[p].lower_bound({h[v], 0});
	--it;
	pii x = *it;
	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]);
	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});
			// cout << v << " : " << ct[v] << " , " << a[v] << " = " << rs[v] << '\n';
			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);
			// cout << p << " : " << ct[p] << " , " << a[p] << " = " << rs[p] << '\n';
			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;
}
/*
10 10
1 2
2 4
2 5
5 7
5 8
1 3
3 6
6 9
6 10
13
1 2 10
1 5 10
1 7 10
1 8 0
2 2
1 2 0
2 7
2 2
1 7 0
2 7
1 7 3
2 8
2 5


92378
1001
66
1
1
1
0
0
11
1
11
1
8
6435
*/
/*
10 10
1 2
2 4
2 5
5 7
5 8
1 3
3 6
6 9
6 10
1
1 7 3
*/
//shrek is love;

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 78624 KB Output is correct
2 Correct 167 ms 78604 KB Output is correct
3 Correct 138 ms 78752 KB Output is correct
4 Correct 114 ms 78632 KB Output is correct
5 Correct 94 ms 74696 KB Output is correct
6 Correct 29 ms 53340 KB Output is correct
7 Correct 28 ms 53104 KB Output is correct
8 Correct 28 ms 53044 KB Output is correct
9 Correct 127 ms 71136 KB Output is correct
10 Correct 130 ms 70860 KB Output is correct
11 Correct 127 ms 70808 KB Output is correct
12 Correct 113 ms 70160 KB Output is correct
13 Correct 109 ms 76908 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 52756 KB Output is correct
2 Incorrect 28 ms 52752 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 78624 KB Output is correct
2 Correct 167 ms 78604 KB Output is correct
3 Correct 138 ms 78752 KB Output is correct
4 Correct 114 ms 78632 KB Output is correct
5 Correct 94 ms 74696 KB Output is correct
6 Correct 29 ms 53340 KB Output is correct
7 Correct 28 ms 53104 KB Output is correct
8 Correct 28 ms 53044 KB Output is correct
9 Correct 127 ms 71136 KB Output is correct
10 Correct 130 ms 70860 KB Output is correct
11 Correct 127 ms 70808 KB Output is correct
12 Correct 113 ms 70160 KB Output is correct
13 Correct 109 ms 76908 KB Output is correct
14 Correct 33 ms 52756 KB Output is correct
15 Incorrect 28 ms 52752 KB Output isn't correct
16 Halted 0 ms 0 KB -