Submission #469396

# Submission time Handle Problem Language Result Execution time Memory
469396 2021-08-31T19:58:46 Z sinamhdv Sumtree (INOI20_sumtree) C++11
100 / 100
525 ms 44516 KB
// INOI20_sumtree
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod = 1000 * 1000 * 1000 + 7;
const int INF = 1e9 + 100;
const ll LINF = 1e18 + 100;

#ifdef DEBUG
#define dbg(x) cout << #x << " = " << (x) << endl << flush;
#define dbgr(s, f) { cout << #s << ": "; for (auto _ = (s); _ != (f); _++) cout << *_ << ' '; cout << endl << flush; }
#else
#define dbg(x) ;
#define dbgr(s, f) ;
#endif
#define fast_io ios::sync_with_stdio(0); cin.tie(0);
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define fr first
#define sc second
#define endl '\n'

const int MAXN = 200100;
const int MAXF = 500100;
const int LOGN = 25;

inline int poww(int a, int b)
{
	int res = 1;
	for (; b; a = (ll)a * a % mod, b /= 2) if (b & 1) res = (ll)res * a % mod;
	return res;
}

int n, rt, q;
vector<int> adj[MAXN];
int bad, ans;
int sttime[MAXN], fntime[MAXN], timer, h[MAXN];
int lbl[MAXN], val[MAXN], cnt[MAXN];
int fact[MAXF], finv[MAXF];
int subtree[MAXN];
int revst[MAXN];

inline int comb(int n, int k)
{
	return (fact[n] * (ll)finv[k] % mod) * finv[n - k] % mod;
}

void dfs1(int v, int par = -1)
{
	subtree[v] = 1;
	sttime[v] = timer++;
	revst[sttime[v]] = v;
	for (int u : adj[v]) if (u != par)
	{
		h[u] = h[v] + 1, dfs1(u, v);
		subtree[v] += subtree[u];
	}
	fntime[v] = timer;
}

struct FEN
{
	ll fen[MAXN];

	inline void add(int i, ll x)
	{
		for (i++; i < MAXN; i += i & -i) fen[i] += x;
	}

	inline ll pget(int i)
	{
		ll res = 0;
		for (i++; i > 0; i -= i & -i) res += fen[i];
		return res;
	}

	inline ll get(int l, int r)
	{
		if (l > r) return 0;
		return pget(r) - pget(l - 1);
	}

} valfen, cntfen;

inline void addans(int i)
{
	if (val[i] < 0) bad++;
	else ans = (ll)ans * comb(val[i] + cnt[i] - 1, cnt[i] - 1) % mod;
}

inline void remans(int i)
{
	if (val[i] < 0) bad--;
	else ans = (ll)ans * poww(comb(val[i] + cnt[i] - 1, cnt[i] - 1), mod - 2) % mod;
}

inline void updateval(int v)
{
	ll nw = lbl[v] - valfen.get(sttime[v] + 1, fntime[v] - 1);
	valfen.add(sttime[v], nw - val[v]);
	val[v] = nw;
}

inline void updatecnt(int v)
{
	int nw = subtree[v] - cntfen.get(sttime[v] + 1, fntime[v] - 1);
	cntfen.add(sttime[v], nw - cnt[v]);
	cnt[v] = nw;
}

int seg[4 * MAXN];

void build(int v = 1, int l = 0, int r = n - 1)
{
	if (l == r)
	{
		if (l == 0) seg[v] = fntime[1];
		return;
	}
	int mid = (r + l) / 2;
	build(2 * v, l, mid);
	build(2 * v + 1, mid + 1, r);
	seg[v] = max(seg[2 * v], seg[2 * v + 1]);
}

void setind(int i, int x, int v = 1, int l = 0, int r = n - 1)
{
	if (l == r) { seg[v] = x; return; }
	int mid = (r + l) / 2;
	if (i <= mid) setind(i, x, 2 * v, l, mid);
	else setind(i, x, 2 * v + 1, mid + 1, r);
	seg[v] = max(seg[2 * v], seg[2 * v + 1]);
}

int segbs(int L, int R, int x, int v = 1, int l = 0, int r = n - 1)
{
	if (l > R || r < L || seg[v] < x) return INF;
	if (l == r) return l;
	int mid = (r + l) / 2;
	int res = segbs(L, R, x, 2 * v + 1, mid + 1, r);
	if (res >= INF) return segbs(L, R, x, 2 * v, l, mid);
	return res;
}

int32_t main(void)
{
	fast_io;

	fact[0] = 1;
	FOR(i, 1, MAXF) fact[i] = fact[i - 1] * (ll)i % mod;
	finv[MAXF - 1] = poww(fact[MAXF - 1], mod - 2);
	for (int i = MAXF - 2; i >= 0; i--) finv[i] = (ll)finv[i + 1] * (i + 1) % mod;

	cin >> n >> rt;
	FOR(i, 0, n - 1)
	{
		int x, y;
		cin >> x >> y;
		adj[x].pb(y);
		adj[y].pb(x);
	}

	dfs1(1);

	ans = comb(n + rt - 1, n - 1);
	cout << ans << endl;

	lbl[1] = val[1] = rt;
	cnt[1] = n;
	valfen.add(0, val[1]);
	cntfen.add(0, cnt[1]);
	build();

	cin >> q;
	while (q--)
	{
		int op, v;
		cin >> op >> v;
		if (op == 1)	// add
		{
			int x;
			cin >> x;
			lbl[v] = x;

			// update anc
			int l = revst[segbs(0, sttime[v] - 1, fntime[v])];
			setind(sttime[v], fntime[v]);

			remans(l);

			// update cnt
			updatecnt(v);
			updatecnt(l);

			// update val
			updateval(v);
			updateval(l);

			addans(v);
			addans(l);
		}
		else	// rem
		{
			setind(sttime[v], 0);
			int l = revst[segbs(0, sttime[v] - 1, fntime[v])];

			remans(l);
			remans(v);

			cntfen.add(sttime[v], -cnt[v]);
			cnt[v] = 0;
			updatecnt(l);

			valfen.add(sttime[v], -val[v]);
			lbl[v] = val[v] = 0;
			updateval(l);

			addans(l);
		}

		ans = (mod + ans % mod) % mod;
		if (bad) cout << "0\n";
		else cout << ans << endl;
	}

	return 0;
}


# Verdict Execution time Memory Grader output
1 Correct 141 ms 28100 KB Output is correct
2 Correct 153 ms 28040 KB Output is correct
3 Correct 141 ms 28132 KB Output is correct
4 Correct 160 ms 28008 KB Output is correct
5 Correct 148 ms 24124 KB Output is correct
6 Correct 13 ms 9420 KB Output is correct
7 Correct 13 ms 9124 KB Output is correct
8 Correct 13 ms 9264 KB Output is correct
9 Correct 145 ms 20544 KB Output is correct
10 Correct 157 ms 20384 KB Output is correct
11 Correct 154 ms 20420 KB Output is correct
12 Correct 137 ms 19828 KB Output is correct
13 Correct 125 ms 27068 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 12 ms 9036 KB Output is correct
2 Correct 12 ms 9032 KB Output is correct
3 Correct 12 ms 9036 KB Output is correct
4 Correct 13 ms 8972 KB Output is correct
5 Correct 13 ms 9072 KB Output is correct
6 Correct 15 ms 9164 KB Output is correct
7 Correct 15 ms 9164 KB Output is correct
8 Correct 15 ms 9228 KB Output is correct
9 Correct 17 ms 9292 KB Output is correct
10 Correct 17 ms 9332 KB Output is correct
11 Correct 17 ms 9372 KB Output is correct
12 Correct 13 ms 9260 KB Output is correct
13 Correct 17 ms 9256 KB Output is correct
14 Correct 17 ms 9292 KB Output is correct
15 Correct 17 ms 9556 KB Output is correct
16 Correct 16 ms 9292 KB Output is correct
17 Correct 17 ms 9256 KB Output is correct
18 Correct 16 ms 9164 KB Output is correct
19 Correct 17 ms 9316 KB Output is correct
20 Correct 14 ms 9228 KB Output is correct
21 Correct 15 ms 9148 KB Output is correct
22 Correct 13 ms 8996 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 195 ms 33816 KB Output is correct
2 Correct 205 ms 34212 KB Output is correct
3 Correct 164 ms 34508 KB Output is correct
4 Correct 248 ms 34992 KB Output is correct
5 Correct 351 ms 31820 KB Output is correct
6 Correct 15 ms 9516 KB Output is correct
7 Correct 15 ms 9292 KB Output is correct
8 Correct 14 ms 9292 KB Output is correct
9 Correct 367 ms 27764 KB Output is correct
10 Correct 313 ms 27572 KB Output is correct
11 Correct 299 ms 27504 KB Output is correct
12 Correct 308 ms 26948 KB Output is correct
13 Correct 341 ms 44516 KB Output is correct
14 Correct 345 ms 44312 KB Output is correct
15 Correct 383 ms 44336 KB Output is correct
16 Correct 348 ms 44348 KB Output is correct
17 Correct 361 ms 44356 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 487 ms 28852 KB Output is correct
2 Correct 475 ms 28776 KB Output is correct
3 Correct 525 ms 28860 KB Output is correct
4 Correct 480 ms 28884 KB Output is correct
5 Correct 510 ms 28044 KB Output is correct
6 Correct 490 ms 28956 KB Output is correct
7 Correct 393 ms 19908 KB Output is correct
8 Correct 358 ms 20048 KB Output is correct
9 Correct 495 ms 28996 KB Output is correct
10 Correct 452 ms 28984 KB Output is correct
11 Correct 458 ms 29176 KB Output is correct
12 Correct 360 ms 20096 KB Output is correct
13 Correct 238 ms 15860 KB Output is correct
14 Correct 266 ms 18084 KB Output is correct
15 Correct 282 ms 18416 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 141 ms 28100 KB Output is correct
2 Correct 153 ms 28040 KB Output is correct
3 Correct 141 ms 28132 KB Output is correct
4 Correct 160 ms 28008 KB Output is correct
5 Correct 148 ms 24124 KB Output is correct
6 Correct 13 ms 9420 KB Output is correct
7 Correct 13 ms 9124 KB Output is correct
8 Correct 13 ms 9264 KB Output is correct
9 Correct 145 ms 20544 KB Output is correct
10 Correct 157 ms 20384 KB Output is correct
11 Correct 154 ms 20420 KB Output is correct
12 Correct 137 ms 19828 KB Output is correct
13 Correct 125 ms 27068 KB Output is correct
14 Correct 12 ms 9036 KB Output is correct
15 Correct 12 ms 9032 KB Output is correct
16 Correct 12 ms 9036 KB Output is correct
17 Correct 13 ms 8972 KB Output is correct
18 Correct 13 ms 9072 KB Output is correct
19 Correct 15 ms 9164 KB Output is correct
20 Correct 15 ms 9164 KB Output is correct
21 Correct 15 ms 9228 KB Output is correct
22 Correct 17 ms 9292 KB Output is correct
23 Correct 17 ms 9332 KB Output is correct
24 Correct 17 ms 9372 KB Output is correct
25 Correct 13 ms 9260 KB Output is correct
26 Correct 17 ms 9256 KB Output is correct
27 Correct 17 ms 9292 KB Output is correct
28 Correct 17 ms 9556 KB Output is correct
29 Correct 16 ms 9292 KB Output is correct
30 Correct 17 ms 9256 KB Output is correct
31 Correct 16 ms 9164 KB Output is correct
32 Correct 17 ms 9316 KB Output is correct
33 Correct 14 ms 9228 KB Output is correct
34 Correct 15 ms 9148 KB Output is correct
35 Correct 13 ms 8996 KB Output is correct
36 Correct 195 ms 33816 KB Output is correct
37 Correct 205 ms 34212 KB Output is correct
38 Correct 164 ms 34508 KB Output is correct
39 Correct 248 ms 34992 KB Output is correct
40 Correct 351 ms 31820 KB Output is correct
41 Correct 15 ms 9516 KB Output is correct
42 Correct 15 ms 9292 KB Output is correct
43 Correct 14 ms 9292 KB Output is correct
44 Correct 367 ms 27764 KB Output is correct
45 Correct 313 ms 27572 KB Output is correct
46 Correct 299 ms 27504 KB Output is correct
47 Correct 308 ms 26948 KB Output is correct
48 Correct 341 ms 44516 KB Output is correct
49 Correct 345 ms 44312 KB Output is correct
50 Correct 383 ms 44336 KB Output is correct
51 Correct 348 ms 44348 KB Output is correct
52 Correct 361 ms 44356 KB Output is correct
53 Correct 487 ms 28852 KB Output is correct
54 Correct 475 ms 28776 KB Output is correct
55 Correct 525 ms 28860 KB Output is correct
56 Correct 480 ms 28884 KB Output is correct
57 Correct 510 ms 28044 KB Output is correct
58 Correct 490 ms 28956 KB Output is correct
59 Correct 393 ms 19908 KB Output is correct
60 Correct 358 ms 20048 KB Output is correct
61 Correct 495 ms 28996 KB Output is correct
62 Correct 452 ms 28984 KB Output is correct
63 Correct 458 ms 29176 KB Output is correct
64 Correct 360 ms 20096 KB Output is correct
65 Correct 238 ms 15860 KB Output is correct
66 Correct 266 ms 18084 KB Output is correct
67 Correct 282 ms 18416 KB Output is correct
68 Correct 12 ms 8944 KB Output is correct
69 Correct 12 ms 9036 KB Output is correct
70 Correct 484 ms 36504 KB Output is correct
71 Correct 481 ms 36588 KB Output is correct
72 Correct 482 ms 36680 KB Output is correct
73 Correct 478 ms 36580 KB Output is correct
74 Correct 482 ms 36620 KB Output is correct
75 Correct 480 ms 32680 KB Output is correct
76 Correct 448 ms 29088 KB Output is correct
77 Correct 490 ms 28856 KB Output is correct
78 Correct 508 ms 27892 KB Output is correct
79 Correct 506 ms 32672 KB Output is correct
80 Correct 480 ms 31908 KB Output is correct
81 Correct 499 ms 32748 KB Output is correct
82 Correct 349 ms 23656 KB Output is correct
83 Correct 365 ms 29872 KB Output is correct
84 Correct 339 ms 29360 KB Output is correct
85 Correct 330 ms 29116 KB Output is correct