Submission #469396

#	Time	Username	Problem	Language	Result	Execution time	Memory
469396		sinamhdv	Sumtree (INOI20_sumtree)	C++11	100 / 100	525 ms	44516 KiB

Main

// 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;
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 30 / 30