Submission #633722

#	Time	Username	Problem	Language	Result	Execution time	Memory
633722		NothingXD	Sumtree (INOI20_sumtree)	C++17	100 / 100	808 ms	55180 KiB

Main

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
//typedef __uint128_t L;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
	cerr << " " << H;
	debug_out(T...);
}

#define debug(...) cerr << "(" << #__VA_ARGS__ << "):", debug_out(__VA_ARGS__)
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)
#define F first
#define S second

const int maxn = 5e5 + 10;
const int mod = 1e9 + 7;

int add(int x, int y){
	int res = x + y;
	if (res >= mod) return res - mod;
	if (res < 0) return res + mod;
	return res;
}

int mul(int x, int y){
	return 1ll * x * y % mod;
}

int pwr(int a, int b){
	int res = 1;
	for (; b; b >>= 1, a = 1LL * a * a % mod) if (b & 1) res = 1ll * res * a % mod;
	return res;
}

int r, n, q, cnt, sz[maxn], seg[maxn << 2], st[maxn], en[maxn], ver[maxn], fact[maxn], invfact[maxn], ans, tme;
ll a[maxn], f[maxn], F[maxn];
vector<int> g[maxn];
bool bad[maxn];

int C(int n, int k){
	return mul(fact[n], mul(invfact[k], invfact[n-k]));
}

void dfs(int v, int p = -1){
	st[v] = ++tme;
	ver[tme] = v;
	sz[v] = 1;
	for (auto u: g[v]){
		if (u != p){
			dfs(u, v);
			sz[v] += sz[u];
		}
	}
	en[v] = tme;
}

void add(ll *f, int idx, ll x){
	for (; idx <= n; idx += idx & -idx) f[idx] += x;
}

ll get(ll *f, int idx){
	ll res = 0;
	for (; idx; idx -= idx & -idx) res += f[idx];
	return res;
}

ll get(ll *f, int l, int r){
	if (r < l) return 0;
	return get(f, r) - get(f, l-1);
}

void change(int v, int l, int r, int idx, int val){
	if (idx < l || r <= idx) return;
	if (l + 1 == r){
		seg[v] = val;
		return;
	}
	int mid = (l + r) >> 1;
	change(v << 1, l, mid, idx, val);
	change(v << 1 | 1, mid, r, idx, val);
	seg[v] = max(seg[v << 1], seg[v << 1 | 1]);
}

int find(int v, int l, int r, int ql, int qr, int val){
	if (qr <= l || r <= ql) return -1;
	if (ql <= l && r <= qr && seg[v] < val) return -1;
	if (l + 1 == r) return ver[l];
	int mid = (l + r) >> 1;
	int res = find(v << 1 | 1, mid, r, ql, qr, val);
	if (res == -1) res = find(v << 1, l, mid, ql, qr, val);
	return res;
}

void add(int idx){
	ll X = sz[idx] - get(f, st[idx] + 1, en[idx]);
	ll Y = a[idx] - get(F, st[idx] + 1, en[idx]);
	add(f, st[idx], X);
	add(F, st[idx], Y);
	change(1, 1, n+1, st[idx], en[idx]);
	if (Y < 0){
		bad[idx] = true;
		cnt++;
		return;
	}
	ans = mul(ans, C(X + Y - 1, X - 1));
}

void remove(int idx){
	ll X = get(f, st[idx], st[idx]);
	ll Y = get(F, st[idx], st[idx]);
	if (bad[idx]){
		bad[idx] = false;
		cnt--;
	}
	else{
		ans = mul(ans, pwr(C(X + Y - 1, X - 1), mod - 2));
	}
	add(f, st[idx], -X);
	add(F, st[idx], -Y);
	change(1, 1, n+1, st[idx], 0);
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);

	fact[0] = invfact[0] = 1;
	for (int i = 1; i < maxn; i++){
		fact[i] = 1ll * fact[i-1] * i % mod;
		invfact[i] = pwr(fact[i], mod-2);
	}

	cin >> n >> r;

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

	dfs(1);

	a[1] = r;
	change(1, 1, n+1, 1, n);
	add(f, 1, n);
	add(F, 1, r);
	ans = C(r + n - 1, n-1);
	cout << ans << '\n';

	cin >> q;

	while(q--){
		int t, v; cin >> t >> v;
		if (t == 1){
			int k; cin >> k;
			int u = find(1, 1, n+1, 1, st[v], st[v]);
			remove(u);
			a[v] = k;
			add(v);
			add(u);
		}
		else{
			int u = find(1, 1, n+1, 1, st[v], st[v]);
			remove(u);
			remove(v);
			add(u);
		}
		cout << (cnt == 0? ans : 0) << '\n';
	}


	return 0;
}

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