Submission #469384

#	Time	Username	Problem	Language	Result	Execution time	Memory
469384		sinamhdv	Sumtree (INOI20_sumtree)	C++11	100 / 100	1538 ms	68676 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 lpar[LOGN][MAXN];
int fact[MAXF], finv[MAXF];

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

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

struct FEN
{
	ll fen[MAXN];

	inline void addind(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);
	}

	inline void add(int l, int r, ll x)
	{
		addind(l, x);
		addind(r + 1, -x);
	}

} valfen, ancfen;

struct node
{
	int mn, mincnt, lz;
};

struct SEG
{
	node seg[4 * MAXN];

	inline node mrg(const node &lc, const node &rc)
	{
		node res = {0, 0, -1};
		res.mn = min(lc.mn, rc.mn);
		res.mincnt = 0;
		if (lc.mn == res.mn) res.mincnt += lc.mincnt;
		if (rc.mn == res.mn) res.mincnt += rc.mincnt;
		return res;
	}

	inline void pushdown(int v)
	{
		if (seg[v].lz == -1) return;
		int mn = min(seg[2 * v].mn, seg[2 * v + 1].mn);
		FOR(t, 2 * v, 2 * v + 2)
		{
			if (seg[t].mn == mn) seg[t].mn = seg[t].lz = seg[v].lz;
		}
		seg[v].lz = -1;
	}

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

	void rset(int L, int R, int x, int mn, int v = 1, int l = 0, int r = n - 1)
	{
		if (l > R || r < L || seg[v].mn > mn) return;
		if (l >= L && r <= R && seg[v].mn == mn)
		{
			seg[v].mn = seg[v].lz = x;
			return;
		}
		int mid = (r + l) / 2;
		pushdown(v);
		rset(L, R, x, mn, 2 * v, l, mid);
		rset(L, R, x, mn, 2 * v + 1, mid + 1, r);
		seg[v] = mrg(seg[2 * v], seg[2 * v + 1]);
	}

	node getmin(int L, int R, int v = 1, int l = 0, int r = n - 1)
	{
		if (l > R || r < L) return {INF, 0, 0};
		if (l >= L && r <= R) return seg[v];
		int mid = (r + l) / 2;
		pushdown(v);
		return mrg(getmin(L, R, 2 * v, l, mid), getmin(L, R, 2 * v + 1, mid + 1, r));
	}

} seg;

inline int getpar(int x, int d)
{
	FOR(i, 0, LOGN) if (d >> i & 1) x = lpar[i][x];
	return x;
}

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.addind(sttime[v], nw - val[v]);
	val[v] = nw;
}

inline int findanc(int v)
{
	int l = 0, r = h[v] + 1;
	int cur = ancfen.pget(sttime[v]);
	while (r - l > 1)
	{
		int mid = (r + l) / 2;
		int x = getpar(v, mid);
		if (ancfen.pget(sttime[x]) == cur) l = mid;
		else r = mid;
	}
	return getpar(v, l);
}

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);

	FOR(i, 1, LOGN) FOR(j, 1, n + 1) lpar[i][j] = lpar[i - 1][lpar[i - 1][j]];

	ans = comb(n + rt - 1, n - 1);
	cout << ans << endl;
	ancfen.add(0, n - 1, 1);
	lbl[1] = val[1] = rt;
	cnt[1] = n;
	seg.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 = findanc(v);
			ancfen.add(sttime[v], fntime[v] - 1, 1);

			remans(l);

			// update cnt
			node p = seg.getmin(sttime[v], fntime[v] - 1);
			seg.rset(sttime[v], fntime[v] - 1, sttime[v], p.mn);
			cnt[l] -= p.mincnt;
			cnt[v] += p.mincnt;

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

			addans(v);
			addans(l);
		}
		else	// rem
		{
			ancfen.add(sttime[v], fntime[v] - 1, -1);
			int l = findanc(v);

			remans(l);
			remans(v);

			node p = seg.getmin(sttime[v], fntime[v] - 1);
			seg.rset(sttime[v], fntime[v] - 1, sttime[l], p.mn);
			cnt[l] += p.mincnt;
			cnt[v] = 0;

			valfen.addind(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