Submission #470173

#	Time	Username	Problem	Language	Result	Execution time	Memory
470173		Sohsoh84	Sumtree (INOI20_sumtree)	C++14	100 / 100	880 ms	93636 KiB

Main

// orz
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

#define all(x)                      (x).begin(),(x).end()
#define X                           first
#define Y                           second
#define sep                         ' '
#define endl                        '\n'
#define debug(x)                    cerr << #x << ": " <<  x << endl;

const ll MAXN = 1e6 + 10;
const ll MOD = 1e9 + 7;
const ll LOG = 20;

struct Fenwick {
	int fen[MAXN];
	Fenwick() {}

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

	inline int query(int ind) {
		int ans = 0;
		for (++ind; ind > 0; ind -= ind & -ind)
			ans += fen[ind];
		return ans;
	}

	inline void add(int l, int r, int val) {
		if (r < l) return;
		add(l, val);
		add(r + 1, -val);
	}


	inline int query(int l, int r) {
		if (r < l) return 0;
		return query(r) - query(l - 1);
	}

	inline void update(int ind, int val) {
		val -= query(ind, ind);
		add(ind, val);
	}
};


inline ll poww(ll a, ll b) {
	ll ans = 1;
	while (b) {
		if (b & 1) ans = ans * a % MOD;
		a = a * a % MOD;
		b >>= 1;
	}

	return ans;
}

inline ll Inv(ll a) {
	if (a == 0) return 1;
	return poww(a, MOD - 2);
}

// R == 0 ?

set<int> Z;
int n, r, q, sub_g[MAXN], par[MAXN][LOG],
    tin[MAXN], tout[MAXN], T, H[MAXN], R[MAXN];
ll fact[MAXN], inv[MAXN], F[MAXN], ans = 1;
vector<int> adj[MAXN];
Fenwick s_fen, t_fen, p_fen;

void dfs(int v, int p) {
	sub_g[v] = 1;
	par[v][0] = p;
	H[v] = H[p] + 1;
	tin[v] = ++T;

	for (int u : adj[v])
		if (u != p)
			dfs(u, v), sub_g[v] += sub_g[u];
	tout[v] = T;
}

inline ll C(ll k, ll n) {
	if (k < 0 || k > n) return 0;
	return fact[n] * inv[k] % MOD * inv[n - k] % MOD;
}

inline void update(int ind, ll val) {
	if (F[ind] == 0) Z.erase(ind);
	
	if (val == 0) {
		Z.insert(ind);
		ans = ans * Inv(F[ind]) % MOD;
		F[ind] = 0;
		return;
	}

	ans = ans * val % MOD * Inv(F[ind]) % MOD;
	F[ind] = val;
}

inline int Par(int v) {
	int t = p_fen.query(tin[v]);
	for (int i = LOG - 1; i >= 0; i--)
		if (p_fen.query(tin[par[v][i]]) == t)
			v = par[v][i];
	return par[v][0];
}

inline void add(int v, int r) {
	R[v] = r;
	p_fen.add(tin[v] + 1, tout[v], 1);
	r -= t_fen.query(tin[v] + 1, tout[v]);
	t_fen.add(tin[v], r);
	
	int s = sub_g[v] - s_fen.query(tin[v] + 1, tout[v]);
	s_fen.add(tin[v], s);
	
	update(v, C(s - 1, s + r - 1));
}

inline void recalc(int v) {
	int r = R[v];
	r -= t_fen.query(tin[v] + 1, tout[v]);
	t_fen.update(tin[v], r);
	
	int s = sub_g[v] - s_fen.query(tin[v] + 1, tout[v]);
	s_fen.update(tin[v], s);
	
	update(v, C(s - 1, s + r - 1));
}

inline void remove(int v) {
	p_fen.add(tin[v] + 1, tout[v], -1);
	s_fen.update(tin[v], 0);
	t_fen.update(tin[v], 0);
	R[v] = 1;
	update(v, 1);
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	fact[0] = inv[0] = 1;
	for (int i = 1; i < MAXN; i++) 
		fact[i] = fact[i - 1] * i % MOD, inv[i] = Inv(fact[i]);
	fill(F, F + MAXN, 1);

	cin >> n >> r;
	for (int i = 1; i < n; i++) {
		int u, v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);	
	}


	dfs(1, 0);
	for (int i = 1; i < LOG; i++)
		for (int v = 1; v <= n; v++)
			par[v][i] = par[par[v][i - 1]][i - 1];
	
	add(1, r);

	cout << (Z.empty() ? ans : 0) << endl;
	cin >> q;
	while (q--) {
		int c;
		cin >> c;
		if (c == 1) {
			int v, u, p;
			cin >> v >> u;
			add(v, u);
			p = Par(v);
			recalc(p);
		} else {
			int v, p;
			cin >> v;
			p = Par(v);
		
			remove(v);
			recalc(p);
		}

		cout << (Z.empty() ? ans : 0) << endl;
	}
	return 0;
}

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