oj.uz

Submission #789509

# Submission time Handle Problem Language Result Execution time Memory
789509 2023-07-21T12:56:15 Z MISM06 Sumtree (INOI20_sumtree) C++14
10 / 100
 333 ms 87160 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];
ll a[N], st[N], en[N], timer = 0, ct[N], c0;
set < pii > 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;
	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';
}
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);
	}
	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({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 = choose(a[v] + ct[v] - 1, ct[v] - 1);
			ans.upd(v, rs);
			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]);
			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({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]);
			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 111 ms 83576 KB Output is correct
2 Correct 124 ms 83544 KB Output is correct
3 Correct 123 ms 83532 KB Output is correct
4 Correct 115 ms 83520 KB Output is correct
5 Correct 93 ms 79628 KB Output is correct
6 Correct 26 ms 53420 KB Output is correct
7 Correct 25 ms 53076 KB Output is correct
8 Correct 26 ms 53088 KB Output is correct
9 Correct 127 ms 76044 KB Output is correct
10 Correct 127 ms 75800 KB Output is correct
11 Correct 110 ms 75692 KB Output is correct
12 Correct 107 ms 75052 KB Output is correct
13 Correct 115 ms 81932 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 52816 KB Output is correct
2 Incorrect 25 ms 52744 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 86444 KB Output is correct
2 Incorrect 149 ms 87160 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 83576 KB Output is correct
2 Correct 124 ms 83544 KB Output is correct
3 Correct 123 ms 83532 KB Output is correct
4 Correct 115 ms 83520 KB Output is correct
5 Correct 93 ms 79628 KB Output is correct
6 Correct 26 ms 53420 KB Output is correct
7 Correct 25 ms 53076 KB Output is correct
8 Correct 26 ms 53088 KB Output is correct
9 Correct 127 ms 76044 KB Output is correct
10 Correct 127 ms 75800 KB Output is correct
11 Correct 110 ms 75692 KB Output is correct
12 Correct 107 ms 75052 KB Output is correct
13 Correct 115 ms 81932 KB Output is correct
14 Correct 25 ms 52816 KB Output is correct
15 Incorrect 25 ms 52744 KB Output isn't correct
16 Halted 0 ms 0 KB -