Submission #417202

#	Time	Username	Problem	Language	Result	Execution time	Memory
417202		parsabahrami	Sumtree (INOI20_sumtree)	C++17	10 / 100	553 ms	116596 KiB

Main

#include <bits/stdc++.h>

using namespace std;
typedef long long int ll;
typedef pair<int, int> pii; 

#define SZ(x) (int) (x).size();
#define F first
#define S second
#define lc id << 1
#define rc lc | 1

int Pow(int a, int b, int md, int ret = 1) {
	for (; b; b >>= 1, a = 1ll * a * a % md) 
		if (b & 1) ret = 1ll * ret * a % md;
	return ret;
}

const int N = 5e5 + 10, MOD = 1e9 + 7;
int F[N], St[N], Ft[N], I[N], hv[N], hd[N], S[N], P[N], val[N], H[N], n, q, r, timer;
vector<int> adj[N]; int seg[N << 2], lz[N << 2]; set<pii> st[N]; int ret;

void shift(int id, int l, int r) {
	seg[id] += lz[id];
	if (r - l > 1) 
		lz[lc] += lz[id], lz[rc] += lz[id];
	lz[id] = 0;
}

void upd(int ql, int qr, int x, int id = 1, int l = 0, int r = n) {
	shift(id, l, r);
	if (qr <= l || r <= ql) return;
	if (ql <= l && r <= qr) { lz[id] += x; return shift(id, l, r); }
	int md = (l + r) >> 1;
	upd(ql, qr, x, lc, l, md), upd(ql, qr, x, rc, md, r);
	seg[id] = min(seg[lc], seg[rc]);
}

int get(int p, int id = 1, int l = 0, int r = n) {
	shift(id, l, r);
	if (r - l < 2) { return seg[id]; }
	int md = (l + r) >> 1;
	return p < md ? get(p, lc, l, md) : get(p, rc, md, r);
}

void preDFS(int v, int p = -1) {
	S[v] = 1; P[v] = p;
	for (int u : adj[v]) 
		if (u != p) { H[u] = H[v] + 1, preDFS(u, v), S[v] += S[u];
			if (S[hv[v]] < S[u]) hv[v] = u; }
}

void hldDFS(int v, int p = -1) {
	if (!~p) hd[v] = v;
	St[v] = timer++;
	if (hv[v]) 
		hd[hv[v]] = hd[v], hldDFS(hv[v], v);
	for (int u : adj[v])
		if (u != p && u != hv[v]) 
			hldDFS(hd[u] = u, v);
	Ft[v] = timer;
}

int C(int x, int y) {
	if (x < y || y < 0) return 0;
	return F[x] * 1ll * I[y] % MOD * I[x - y] % MOD;
}

int main() {
	scanf("%d%d", &n, &r);
	F[0] = 1; st[1].insert(pii(0, 1)); val[1] = r;
	for (int i = 1; i < N; i++)  
		F[i] = 1ll * F[i - 1] * i % MOD;
	I[N - 1] = Pow(F[N - 1], MOD - 2, MOD);
	for (int i = N - 1; i; i--) 
		I[i - 1] = 1ll * I[i] * i % MOD;
	for (int i = 1; i < n; i++) {
		int u, v; scanf("%d%d", &u, &v); 
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	preDFS(1); hldDFS(1);
	printf("%d\n", ret = C(r + n - 1, n - 1));
	for (int i = 1; i <= n; i++) 
		upd(St[i], St[i] + 1, S[i]);
	for (scanf("%d", &q); q; q--) {
		int t, v, x; scanf("%d%d", &t, &v);
		if (t < 2) {
			scanf("%d", &x); int sub = get(St[v]);
			ret = 1ll * ret * C((val[v] = x) + sub - 1, sub - 1) % MOD;
			int u = P[v];
			while (st[hd[u]].empty() || st[hd[u]].begin()->F > St[v]) {
				upd(St[hd[u]], St[u] + 1, -sub); 
				u = P[hd[u]]; 
			}
			int pr = prev(st[hd[u]].lower_bound(pii(St[v], -1)))->S;
			st[hd[v]].insert(pii(St[v], v));
			int cpr = get(St[pr]); ret = 1ll * ret * Pow(C(cpr - 1 + val[pr], val[pr]), MOD - 2, MOD) % MOD;
			upd(St[pr], St[u] + 1, -sub); cpr = get(St[pr]); 
			ret = 1ll * ret * C(cpr - 1 + val[pr], val[pr]) % MOD;
		} else {
			int sub = get(St[v]);
			ret = 1ll * ret * Pow(C(sub + val[v] - 1, val[v]), MOD - 2, MOD) % MOD;
			int u = P[v]; st[hd[v]].erase(pii(St[v], v));
			while (st[hd[u]].empty() || st[hd[u]].begin()->F > St[v]) {
				upd(St[hd[u]], St[u] + 1, sub); 
				u = P[hd[u]];
			}
			int pr = prev(st[hd[u]].lower_bound(pii(St[v], -1)))->S;
			int cpr = get(St[pr]); ret = 1ll * ret * Pow(C(cpr - 1 + val[pr], val[pr]), MOD - 2, MOD) % MOD;
			upd(St[pr], St[u] + 1, sub); cpr = get(St[pr]); 
			ret = 1ll * ret * C(cpr - 1 + val[pr], val[pr]) % MOD;
		}
		printf("%d\n", ret);
	}
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:70:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |  scanf("%d%d", &n, &r);
      |  ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:78:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |   int u, v; scanf("%d%d", &u, &v);
      |             ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:86:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |  for (scanf("%d", &q); q; q--) {
      |       ~~~~~^~~~~~~~~~
Main.cpp:87:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |   int t, v, x; scanf("%d%d", &t, &v);
      |                ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:89:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |    scanf("%d", &x); int sub = get(St[v]);
      |    ~~~~~^~~~~~~~~~

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