Submission #417366

#	Time	Username	Problem	Language	Result	Execution time	Memory
417366		parsabahrami	Sumtree (INOI20_sumtree)	C++17	50 / 100	1415 ms	112728 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

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]; set<pii> st[N]; int ret;
struct node {
	int d, lz; node *lc, *rc; 

	node() : d(0), lz(0), lc(nullptr), rc(nullptr) {}

	void bld(int l = 0, int r = n) {
		if (r - l < 2) return;
		lc = new node(); rc = new node();
		int md = (l + r) >> 1;
		lc->bld(l, md), rc->bld(md, r);
	}

	void shift() { 
		if (!lz) return;
		d += lz;
		if (lc) lc->lz += lz;
		if (rc) rc->lz += lz;
		lz = 0;
	}

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

	int get(int p, int l = 0, int r = n) {
        shift();
		if (r - l < 2) return d;
		int md = (l + r) >> 1;
		return p < md ? lc->get(p, l, md) : rc->get(p, md, r);
	}
};
node *A, *B;

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);
	} 
	A = new node(), B = new node(); A->bld(), B->bld(); B->upd(0, 1, R);
	preDFS(1); hldDFS(1);
	printf("%d\n", ret = C(R + n - 1, n - 1));
	for (int i = 1; i <= n; i++) 
		A->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 = A->get(St[v]); B->upd(St[v], St[v] + 1, x);
			int y = B->get(St[v]); val[v] = x;
			ret = 1ll * ret * C(y + sub - 1, sub - 1) % MOD;
			int u = P[v];
			while (st[hd[u]].empty() || st[hd[u]].begin()->F > St[u]) {
				A->upd(St[hd[u]], St[u] + 1, -sub); 
				B->upd(St[hd[u]], St[u] + 1, -y);
				u = P[hd[u]]; 
			}
			int pr = prev(st[hd[u]].lower_bound(pii(St[u], n + 1)))->S;
			st[hd[v]].insert(pii(St[v], v));
			int cpr = A->get(St[pr]); int z = B->get(St[pr]);
			ret = 1ll * ret * Pow(C(cpr - 1 + z, z), MOD - 2, MOD) % MOD;
			A->upd(St[pr], St[u] + 1, -sub); B->upd(St[pr], St[u] + 1, -y); 
			z = B->get(St[pr]); cpr = A->get(St[pr]);
			ret = 1ll * ret * C(cpr - 1 + z, z) % MOD;
		} else {
            int sub = A->get(St[v]), y = B->get(St[v]);
			ret = 1ll * ret * Pow(C(y + sub - 1, sub - 1), MOD - 2, MOD) % MOD;
			int u = P[v]; st[hd[v]].erase({St[v], v});
			while (st[hd[u]].empty() || st[hd[u]].begin()->F > St[u]) {
				A->upd(St[hd[u]], St[u] + 1, sub); 
				B->upd(St[hd[u]], St[u] + 1, y);
				u = P[hd[u]]; 
			}
			int pr = prev(st[hd[u]].lower_bound(pii(St[u], n + 1)))->S;
			int cpr = A->get(St[pr]); int z = B->get(St[pr]); 
			ret = 1ll * ret * Pow(C(cpr - 1 + z, z), MOD - 2, MOD) % MOD;
			A->upd(St[pr], St[u] + 1, sub); B->upd(St[pr], St[u] + 1, y); 
			z = B->get(St[pr]); cpr = A->get(St[pr]); 
			ret = 1ll * ret * C(cpr - 1 + z, z) % MOD; B->upd(St[v], St[v] + 1, -val[v]);
		}
		printf("%d\n", ret);
	}
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:83:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |  scanf("%d%d", &n, &R);
      |  ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:91:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |   int u, v; scanf("%d%d", &u, &v);
      |             ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:100:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  100 |  for (scanf("%d", &q); q; q--) {
      |       ~~~~~^~~~~~~~~~
Main.cpp:101:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  101 |   int t, v, x; scanf("%d%d", &t, &v);
      |                ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:103:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  103 |    scanf("%d", &x); int sub = A->get(St[v]); B->upd(St[v], St[v] + 1, x);
      |    ~~~~~^~~~~~~~~~

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