oj.uz

Submission #789256

# Submission time Handle Problem Language Result Execution time Memory
789256 2023-07-21T08:41:15 Z MISM06 Sumtree (INOI20_sumtree) C++14
10 / 100
 715 ms 88028 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;
	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});
			// 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 241 ms 84240 KB Output is correct
2 Correct 235 ms 84248 KB Output is correct
3 Correct 214 ms 84172 KB Output is correct
4 Correct 215 ms 84236 KB Output is correct
5 Correct 191 ms 80336 KB Output is correct
6 Correct 35 ms 57204 KB Output is correct
7 Correct 31 ms 56916 KB Output is correct
8 Correct 38 ms 57000 KB Output is correct
9 Correct 221 ms 76576 KB Output is correct
10 Correct 198 ms 76416 KB Output is correct
11 Correct 205 ms 76576 KB Output is correct
12 Correct 233 ms 75528 KB Output is correct
13 Correct 176 ms 82256 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 56700 KB Output is correct
2 Incorrect 31 ms 56644 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 245 ms 87040 KB Output is correct
2 Incorrect 286 ms 88028 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 84240 KB Output is correct
2 Correct 235 ms 84248 KB Output is correct
3 Correct 214 ms 84172 KB Output is correct
4 Correct 215 ms 84236 KB Output is correct
5 Correct 191 ms 80336 KB Output is correct
6 Correct 35 ms 57204 KB Output is correct
7 Correct 31 ms 56916 KB Output is correct
8 Correct 38 ms 57000 KB Output is correct
9 Correct 221 ms 76576 KB Output is correct
10 Correct 198 ms 76416 KB Output is correct
11 Correct 205 ms 76576 KB Output is correct
12 Correct 233 ms 75528 KB Output is correct
13 Correct 176 ms 82256 KB Output is correct
14 Correct 34 ms 56700 KB Output is correct
15 Incorrect 31 ms 56644 KB Output isn't correct
16 Halted 0 ms 0 KB -