oj.uz

Submission #789212

# Submission time Handle Problem Language Result Execution time Memory
789212 2023-07-21T07:51:37 Z MISM06 Sumtree (INOI20_sumtree) C++17
10 / 100
 310 ms 57112 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 113 ms 53524 KB Output is correct
2 Correct 106 ms 53488 KB Output is correct
3 Correct 112 ms 53504 KB Output is correct
4 Correct 115 ms 53568 KB Output is correct
5 Correct 88 ms 49516 KB Output is correct
6 Correct 18 ms 29012 KB Output is correct
7 Correct 18 ms 28756 KB Output is correct
8 Correct 20 ms 28756 KB Output is correct
9 Correct 131 ms 45892 KB Output is correct
10 Correct 107 ms 45792 KB Output is correct
11 Correct 108 ms 45828 KB Output is correct
12 Correct 126 ms 45068 KB Output is correct
13 Correct 93 ms 51852 KB Output is correct

Subtask #2
0 / 20.0

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

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 56308 KB Output is correct
2 Incorrect 164 ms 57112 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 53524 KB Output is correct
2 Correct 106 ms 53488 KB Output is correct
3 Correct 112 ms 53504 KB Output is correct
4 Correct 115 ms 53568 KB Output is correct
5 Correct 88 ms 49516 KB Output is correct
6 Correct 18 ms 29012 KB Output is correct
7 Correct 18 ms 28756 KB Output is correct
8 Correct 20 ms 28756 KB Output is correct
9 Correct 131 ms 45892 KB Output is correct
10 Correct 107 ms 45792 KB Output is correct
11 Correct 108 ms 45828 KB Output is correct
12 Correct 126 ms 45068 KB Output is correct
13 Correct 93 ms 51852 KB Output is correct
14 Correct 18 ms 28500 KB Output is correct
15 Incorrect 21 ms 28536 KB Output isn't correct
16 Halted 0 ms 0 KB -