oj.uz

Submission #789546

# Submission time Handle Problem Language Result Execution time Memory
789546 2023-07-21T13:30:05 Z MISM06 Sumtree (INOI20_sumtree) C++14
100 / 100
 420 ms 111532 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], rst[N];
ll a[N], st[N], en[N], timer = 0, ct[N], c0;
set < int > s[N];
vector < int > g[N];

struct segtree {
	ll seg[N << 2];
	void build (int v = 1, int tl = 1, int tr = n) {
		if (tl == tr) {
			seg[v] = 1;
			return;
		} kids;
		build(cl, tl, mid);
		build(cr, mid + 1, tr);
		seg[v] = mul(seg[cl], seg[cr]);
	}
	void upd (int idx, ll val, int v = 1, int tl = 1, int tr = n) {
		if (tl == tr) {
			seg[v] = val;
			return;
		} kids;
		if (idx <= mid) upd(idx, val, cl, tl, mid);
		else upd(idx, val, cr, mid + 1, tr);
		seg[v] = mul(seg[cl], seg[cr]);
	}
	ll ask () {
		return seg[1];
	}
} ans;

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; rst[st[v]] = v;
	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 () {
	cout << ans.ask() << '\n';
}
bool is[N];
int find_par (int v) {
	int p = chp[v];
	if (s[p].sze != 0) {
		auto it = s[p].lower_bound(st[v]);
		if (it != s[p].begin()) {
			--it;
			return rst[*it];
		}
	}
	v = par[p];
	p = chp[par[p]];
	while (true) {

		if (s[p].sze != 0) {
			auto it = s[p].upper_bound(st[v]);
			if (it != s[p].begin()) {
				--it;
				return rst[*it];
			}
		}
		v = par[p];
		p = chp[par[p]];
	}
	// v = par[v];
	// while(!is[v]) {
	// 	v = par[v];
	// }
	// return v;	
}

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);
	}
	sub[0] = -1;
	ans.build();
	chp[1] = 1;
	dfs0(1, 0);
	dfs(1, 0);
	ct[1] = n; f1.upd(st[1], n); f2.upd(st[1], a[1]);
	ll rs = choose(a[1] + ct[1] - 1, ct[1] - 1);
	ans.upd(1, rs);
	s[chp[1]].insert(st[1]);
	is[1] = 1;
	out();
	int q; cin >> q;
	while (q--) {
		int t; cin >> t;
		if (t == 1) {
			ll 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 = choose(a[v] + ct[v] - 1, ct[v] - 1);
			ans.upd(v, rs);
			s[chp[v]].insert(st[v]);
			is[v] = 1;

			int p = find_par(v);
			// cout << "p = " << p << '\n';
			ct[p] -= ct[v];
			f1.upd(st[p], -ct[v]);
			a[p] -= a[v];
			f2.upd(st[p], -a[v]);
			rs = choose(a[p] + ct[p] - 1, ct[p] - 1);
			ans.upd(p, rs);
			out();

		} else {
			int v; cin >> v;
			f1.upd(st[v], -ct[v]);
			f2.upd(st[v], -a[v]);
			rs = 1;
			ans.upd(v, rs);
			s[chp[v]].erase(st[v]);
			is[v] = 0;

			int p = find_par(v);
			// cout << "p = " << p << '\n';
			ct[p] += ct[v];
			f1.upd(st[p], ct[v]);
			a[p] += a[v];
			f2.upd(st[p], a[v]);
			rs = choose(a[p] + ct[p] - 1, ct[p] - 1);
			ans.upd(p, rs);
			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
*/
//shrek is love;

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 85008 KB Output is correct
2 Correct 116 ms 84948 KB Output is correct
3 Correct 120 ms 85180 KB Output is correct
4 Correct 149 ms 85148 KB Output is correct
5 Correct 97 ms 81080 KB Output is correct
6 Correct 27 ms 53324 KB Output is correct
7 Correct 28 ms 53196 KB Output is correct
8 Correct 26 ms 53200 KB Output is correct
9 Correct 129 ms 77260 KB Output is correct
10 Correct 142 ms 77540 KB Output is correct
11 Correct 111 ms 77516 KB Output is correct
12 Correct 109 ms 76280 KB Output is correct
13 Correct 100 ms 82876 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 52824 KB Output is correct
2 Correct 25 ms 52848 KB Output is correct
3 Correct 25 ms 52812 KB Output is correct
4 Correct 26 ms 52772 KB Output is correct
5 Correct 26 ms 52948 KB Output is correct
6 Correct 34 ms 53176 KB Output is correct
7 Correct 29 ms 53104 KB Output is correct
8 Correct 34 ms 53116 KB Output is correct
9 Correct 29 ms 53320 KB Output is correct
10 Correct 29 ms 53376 KB Output is correct
11 Correct 29 ms 53384 KB Output is correct
12 Correct 27 ms 53300 KB Output is correct
13 Correct 31 ms 53348 KB Output is correct
14 Correct 30 ms 53304 KB Output is correct
15 Correct 29 ms 53596 KB Output is correct
16 Correct 28 ms 53240 KB Output is correct
17 Correct 29 ms 53388 KB Output is correct
18 Correct 27 ms 53076 KB Output is correct
19 Correct 28 ms 53332 KB Output is correct
20 Correct 31 ms 53168 KB Output is correct
21 Correct 28 ms 53076 KB Output is correct
22 Correct 30 ms 52892 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 87984 KB Output is correct
2 Correct 150 ms 89172 KB Output is correct
3 Correct 133 ms 89752 KB Output is correct
4 Correct 186 ms 90628 KB Output is correct
5 Correct 299 ms 91340 KB Output is correct
6 Correct 29 ms 53492 KB Output is correct
7 Correct 28 ms 53332 KB Output is correct
8 Correct 28 ms 53356 KB Output is correct
9 Correct 304 ms 87488 KB Output is correct
10 Correct 254 ms 86264 KB Output is correct
11 Correct 250 ms 85828 KB Output is correct
12 Correct 289 ms 86236 KB Output is correct
13 Correct 330 ms 111180 KB Output is correct
14 Correct 283 ms 111504 KB Output is correct
15 Correct 274 ms 111532 KB Output is correct
16 Correct 318 ms 111408 KB Output is correct
17 Correct 308 ms 111412 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 342 ms 82864 KB Output is correct
2 Correct 332 ms 83632 KB Output is correct
3 Correct 327 ms 83700 KB Output is correct
4 Correct 332 ms 83568 KB Output is correct
5 Correct 308 ms 82176 KB Output is correct
6 Correct 311 ms 82144 KB Output is correct
7 Correct 232 ms 68940 KB Output is correct
8 Correct 261 ms 68956 KB Output is correct
9 Correct 330 ms 83400 KB Output is correct
10 Correct 340 ms 82224 KB Output is correct
11 Correct 344 ms 83248 KB Output is correct
12 Correct 227 ms 68868 KB Output is correct
13 Correct 196 ms 67200 KB Output is correct
14 Correct 219 ms 68200 KB Output is correct
15 Correct 202 ms 68704 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 85008 KB Output is correct
2 Correct 116 ms 84948 KB Output is correct
3 Correct 120 ms 85180 KB Output is correct
4 Correct 149 ms 85148 KB Output is correct
5 Correct 97 ms 81080 KB Output is correct
6 Correct 27 ms 53324 KB Output is correct
7 Correct 28 ms 53196 KB Output is correct
8 Correct 26 ms 53200 KB Output is correct
9 Correct 129 ms 77260 KB Output is correct
10 Correct 142 ms 77540 KB Output is correct
11 Correct 111 ms 77516 KB Output is correct
12 Correct 109 ms 76280 KB Output is correct
13 Correct 100 ms 82876 KB Output is correct
14 Correct 25 ms 52824 KB Output is correct
15 Correct 25 ms 52848 KB Output is correct
16 Correct 25 ms 52812 KB Output is correct
17 Correct 26 ms 52772 KB Output is correct
18 Correct 26 ms 52948 KB Output is correct
19 Correct 34 ms 53176 KB Output is correct
20 Correct 29 ms 53104 KB Output is correct
21 Correct 34 ms 53116 KB Output is correct
22 Correct 29 ms 53320 KB Output is correct
23 Correct 29 ms 53376 KB Output is correct
24 Correct 29 ms 53384 KB Output is correct
25 Correct 27 ms 53300 KB Output is correct
26 Correct 31 ms 53348 KB Output is correct
27 Correct 30 ms 53304 KB Output is correct
28 Correct 29 ms 53596 KB Output is correct
29 Correct 28 ms 53240 KB Output is correct
30 Correct 29 ms 53388 KB Output is correct
31 Correct 27 ms 53076 KB Output is correct
32 Correct 28 ms 53332 KB Output is correct
33 Correct 31 ms 53168 KB Output is correct
34 Correct 28 ms 53076 KB Output is correct
35 Correct 30 ms 52892 KB Output is correct
36 Correct 154 ms 87984 KB Output is correct
37 Correct 150 ms 89172 KB Output is correct
38 Correct 133 ms 89752 KB Output is correct
39 Correct 186 ms 90628 KB Output is correct
40 Correct 299 ms 91340 KB Output is correct
41 Correct 29 ms 53492 KB Output is correct
42 Correct 28 ms 53332 KB Output is correct
43 Correct 28 ms 53356 KB Output is correct
44 Correct 304 ms 87488 KB Output is correct
45 Correct 254 ms 86264 KB Output is correct
46 Correct 250 ms 85828 KB Output is correct
47 Correct 289 ms 86236 KB Output is correct
48 Correct 330 ms 111180 KB Output is correct
49 Correct 283 ms 111504 KB Output is correct
50 Correct 274 ms 111532 KB Output is correct
51 Correct 318 ms 111408 KB Output is correct
52 Correct 308 ms 111412 KB Output is correct
53 Correct 342 ms 82864 KB Output is correct
54 Correct 332 ms 83632 KB Output is correct
55 Correct 327 ms 83700 KB Output is correct
56 Correct 332 ms 83568 KB Output is correct
57 Correct 308 ms 82176 KB Output is correct
58 Correct 311 ms 82144 KB Output is correct
59 Correct 232 ms 68940 KB Output is correct
60 Correct 261 ms 68956 KB Output is correct
61 Correct 330 ms 83400 KB Output is correct
62 Correct 340 ms 82224 KB Output is correct
63 Correct 344 ms 83248 KB Output is correct
64 Correct 227 ms 68868 KB Output is correct
65 Correct 196 ms 67200 KB Output is correct
66 Correct 219 ms 68200 KB Output is correct
67 Correct 202 ms 68704 KB Output is correct
68 Correct 29 ms 52768 KB Output is correct
69 Correct 25 ms 52840 KB Output is correct
70 Correct 360 ms 93628 KB Output is correct
71 Correct 368 ms 93616 KB Output is correct
72 Correct 341 ms 93516 KB Output is correct
73 Correct 334 ms 93508 KB Output is correct
74 Correct 355 ms 93388 KB Output is correct
75 Correct 413 ms 89588 KB Output is correct
76 Correct 340 ms 85776 KB Output is correct
77 Correct 372 ms 85968 KB Output is correct
78 Correct 420 ms 86860 KB Output is correct
79 Correct 373 ms 89532 KB Output is correct
80 Correct 344 ms 88324 KB Output is correct
81 Correct 350 ms 89212 KB Output is correct
82 Correct 259 ms 81864 KB Output is correct
83 Correct 250 ms 89840 KB Output is correct
84 Correct 261 ms 89048 KB Output is correct
85 Correct 244 ms 88872 KB Output is correct