Submission #417938

#	Time	Username	Problem	Language	Result	Execution time	Memory
417938		parsabahrami	Sumtree (INOI20_sumtree)	C++17	100 / 100	1494 ms	129148 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 int   ll

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]; ll ret; int cnt = 0;
struct node {
	ll 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, ll 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);
	}

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

void mul(int x) {
    if (!x) cnt++;
    else ret = x * ret % MOD;
}

void div(int x) {
    if (!x) cnt--;
    else ret = Pow(x, MOD - 2, MOD) * ret % MOD;
}

int32_t main() {
	scanf("%lld%lld", &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("%lld%lld", &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("%lld\n", C(R + n - 1, n - 1)); 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("%lld", &q); q; q--) {
		int t, v, x; scanf("%lld%lld", &t, &v);
		if (t < 2) {
			scanf("%lld", &x); ll sub = A->get(St[v]); B->upd(St[v], St[v] + 1, x);
			ll y = B->get(St[v]); val[v] = x;
            mul(C(y + sub - 1, y));
			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]]; 
			}
			ll pr = prev(st[hd[u]].lower_bound(pii(St[u], n + 1)))->S;
			st[hd[v]].insert(pii(St[v], v));
			ll cpr = A->get(St[pr]); ll z = B->get(St[pr]);
            div(C(cpr - 1 + z, z));
			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]);
            mul(C(cpr - 1 + z, z));
		} else {
            ll sub = A->get(St[v]), y = B->get(St[v]);
            div(C(y + sub - 1, y));
			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]]; 
			}
			ll pr = prev(st[hd[u]].lower_bound(pii(St[u], n + 1)))->S;
			ll cpr = A->get(St[pr]); ll z = B->get(St[pr]); 
            div(C(cpr - 1 + z, z));
			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]); 
			mul(C(cpr - 1 + z, z)); B->upd(St[v], St[v] + 1, -val[v]);
		}
        if (cnt) printf("0\n");
        else printf("%lld\n", ret);
	}
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int32_t main()':
Main.cpp:94:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |  scanf("%lld%lld", &n, &R);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~
Main.cpp:102:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |   int u, v; scanf("%lld%lld", &u, &v);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~
Main.cpp:111:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |  for (scanf("%lld", &q); q; q--) {
      |       ~~~~~^~~~~~~~~~~~
Main.cpp:112:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  112 |   int t, v, x; scanf("%lld%lld", &t, &v);
      |                ~~~~~^~~~~~~~~~~~~~~~~~~~
Main.cpp:114:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  114 |    scanf("%lld", &x); ll 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: 20 / 20
• Subtask 5: 30 / 30