Submission #469345

#	Time	Username	Problem	Language	Result	Execution time	Memory
469345		sinamhdv	Sumtree (INOI20_sumtree)	C++11	10 / 100	3065 ms	92280 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, mncnt, lz;
};

struct SEG
{
	int seg[4 * MAXN];

	void rset(int L, int R, int x)//, int v = 1, int l = 0, int r = n - 1)
	{
		int mn = *min_element(seg + L, seg + R + 1);
		FOR(i, L, R + 1) if (seg[i] == mn) seg[i] = x;
	}

	pii getmin(int L, int R)
	{
		int mn = *min_element(seg + L, seg + R + 1);
		int cnt = 0;
		FOR(i, L, R + 1) if (seg[i] == mn) cnt++;
		return {mn, cnt};
	}

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

	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
			pii p = seg.getmin(sttime[v], fntime[v] - 1);
			if (p.fr == sttime[l])
			{
				seg.rset(sttime[v], fntime[v] - 1, sttime[v]);
			}
			cnt[l] -= p.sc;
			cnt[v] += p.sc;

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

			addans(v);
			addans(l);
		}
		else	// rem
		{
			// reset cnt & lbl & val
		}

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

	return 0;
}

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