oj.uz

답안 #464300

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
464300 2021-08-12T19:24:15 Z Return_0 Sumtree (INOI20_sumtree) C++17
10 / 100
 538 ms 102508 KB 
#pragma GCC optimize("Ofast,unroll-loops")
// #pragma comment(linker, "/stack:200000000")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma,tune=native")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef int ll;
typedef long long lol;
typedef long double ld;
typedef pair <ll, ll> pll;

#ifdef SINA
#define dbg(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1> void __f(const char* name, Arg1&& arg1) { cout << name << " : " << arg1 << std::endl; }
template <typename Arg1, typename... Args> void __f (const char* names, Arg1&& arg1, Args&&... args) {
	const char* comma = strchr(names + 1, ',');cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...); }
#define dbg2(x, j, n) cout<< #x << " : "; output((j), (n), x, 1); cout.flush();
#else
#define dbg(...) 0
#define dbg2(x, j, n) 0
#endif
#define SZ(x) ((ll)((x).size()))
#define File(s, t) freopen(s ".txt", "r", stdin); freopen(t ".txt", "w", stdout);
#define input(j, n, a) for (int _i = (j); _i < (n)+(j); _i++) cin>> a[_i];
#define output(j, n, a, t) for (int _i = (j); _i < (n)+(j); _i++) cout<< a[_i] << (((t) && _i != (n)+(j)-1)? ' ' : '\n');
#define kill(x) return cout<< (x) << endl, 0
#define cl const ll
#define fr first
#define sc second
#define lc (v << 1)
#define rc (lc | 1)
#define mid ((l + r) >> 1)
#define All(x) (x).begin(), (x).end()

const lol inf = sizeof(lol) == 4 ? (1e9 + 10) : (3e18), mod = 1e9 + 7, MOD = 998244353;

template <class A,class B> ostream& operator << (ostream& out,const pair<A,B>&a){return out<<'('<<a.first<<", "<<a.second<<')';}
template <class A> ostream& operator << (ostream& out, const vector<A> &a) {
	out<< '['; for (int i = -1; ++i < int(a.size());) out<< a[i] << (i + 1 < int(a.size()) ? ", " : ""); return out<<']'; }
template <class T, typename _t = less <T> > using Tree = tree <T, null_type, _t, rb_tree_tag, tree_order_statistics_node_update>;

cl N = 5e5 + 7;

inline lol bpow (lol x, ll n) { lol t = 1; for (; n; n >>= 1, x = x * x % mod) if (n & 1) t = t * x % mod; return t; }
inline lol Inv (cl &x) { return bpow(x, mod - 2); }

lol f [N], inv [N], ans;
ll tin [N], tout [N], rtin [N], c [N], sz [N], n, r, q, zero, T;
vector <ll> adj [N];

void DFS (cl &v = 1, cl &pr = 0) {
	rtin[tin[v] = ++T] = v;
	for (auto &u : adj[v]) if (u != pr) DFS(u, v);
	tout[v] = T;
}

struct segtree {
	ll l, r, mx;
	segtree *lt, *rt;
	inline segtree (cl &L = 1, cl &R = N - 2) : l(L), r(R), mx(0) {}

	void build () {
		if (l == r) return;
		lt = new segtree (l, mid);
		rt = new segtree (mid + 1, r);
		lt->build();
		rt->build();
	}

	void upd (cl &pos, cl &x) {
		if (l == r) { mx = x; return; }
		if (pos <= lt->r) lt->upd(pos, x);
		else rt->upd(pos, x);
		mx = max(lt->mx, rt->mx);
	}

	ll ask (cl &qr, cl &x) {
		if (qr < l || mx < x) return 0;
		if (l == r) return l;
		if (r <= qr) {
			if (rt->mx >= x) return rt->ask(qr, x);
			return lt->ask(qr, x);
		}
		ll p = rt->ask(qr, x);
		if (!p) p = lt->ask(qr, x);
		return p;
	}
} seg;

struct fenwick {
	ll fen [N];
	inline void add (ll i, cl &x) { for (; i < N; i += i & -i) fen[i] += x; }
	inline ll ask (ll l, ll r) {
		ll ret = 0;
		for (; r; r -= r & -r) ret += fen[r];
		for (l--; l; l -= l & -l) ret -= fen[l];
		return ret;
	}
} fen, fen2;

inline lol nCr (cl &n, cl &r) { return f[n] * inv[r] % mod * inv[n - r] % mod; }

int main ()
{
	cin.tie(0)->sync_with_stdio(false);

	f[0] = 1; for (lol i = 1; i < N; i++) f[i] = f[i - 1] * i % mod;
	inv[N - 1] = Inv(f[N - 1]); for (lol i = N; --i;) inv[i - 1] = inv[i] * i % mod;

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

	DFS();
	seg.r = n; seg.build();
	seg.upd(tin[1], tout[1]);
	c[1] = r; sz[1] = n;
	fen.add(tin[1], c[1]);
	fen2.add(tin[1], sz[1]);

	ans = nCr(c[1] + sz[1] - 1, sz[1] - 1);
	cout<< ans << '\n';

	cin>> q;
	for (ll tp, v; q--;) {
		cin>> tp >> v;
		if (tp == 1) {
			cin>> c[v];
			ll tot = fen.ask(tin[v], tout[v]);
			if (tot > c[v]) c[v] = -1, zero++;
			else {
				c[v] -= tot;
				ll par = rtin[seg.ask(tin[v], tout[v])];
				if (c[v] > c[par]) c[v] = -1, zero++;
				else {
					(ans *= Inv(nCr(c[par] + sz[par] - 1, sz[par] - 1))) %= mod;
					sz[v] = tout[v] - tin[v] + 1 - fen.ask(tin[v], tout[v]);
					sz[par] -= sz[v];
					fen2.add(tin[par], -sz[v]);
					fen2.add(tin[v], sz[v]);				
					c[par] -= c[v];
					fen.add(tin[par], -c[v]);
					fen.add(tin[v], c[v]);
					(ans *= nCr(c[par] + sz[par] - 1, sz[par] - 1)) %= mod;
					(ans *= nCr(c[v] + sz[v] - 1, sz[v] - 1)) %= mod;
					seg.upd(tin[v], tout[v]);
				}
			}
		} else {
			if (!~c[v]) c[v] = 0, zero--;
			else {
				seg.upd(tin[v], 0);
				ll par = rtin[seg.ask(tin[v], tout[v])];
				(ans *= Inv(nCr(c[par] + sz[par] - 1, sz[par] - 1))) %= mod;
				(ans *= Inv(nCr(c[v] + sz[v] - 1, sz[v] - 1))) %= mod;
				sz[par] += sz[v];
				fen2.add(tin[par], sz[v]);
				fen2.add(tin[v], -sz[v]);				
				c[par] += c[v];
				fen.add(tin[par], c[v]);
				fen.add(tin[v], -c[v]);
				(ans *= nCr(c[par] + sz[par] - 1, sz[par] - 1)) %= mod;
			}
		}

		cout<< (zero ? 0LL : ans) << '\n';
	}

	cerr<< "\n" __TIMESTAMP__ " - Time elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";

	return 0;
}
/*
3 2
1 2
2 3
2
1 2 1
2 2

*/

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 163 ms 49528 KB Output is correct
2 Correct 169 ms 49476 KB Output is correct
3 Correct 158 ms 49420 KB Output is correct
4 Correct 162 ms 49488 KB Output is correct
5 Correct 144 ms 48416 KB Output is correct
6 Correct 17 ms 20448 KB Output is correct
7 Correct 17 ms 20416 KB Output is correct
8 Correct 19 ms 20364 KB Output is correct
9 Correct 155 ms 47616 KB Output is correct
10 Correct 163 ms 47452 KB Output is correct
11 Correct 170 ms 47620 KB Output is correct
12 Correct 182 ms 46148 KB Output is correct
13 Correct 138 ms 46772 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 16 ms 19916 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 251 ms 102508 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 538 ms 51136 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 163 ms 49528 KB Output is correct
2 Correct 169 ms 49476 KB Output is correct
3 Correct 158 ms 49420 KB Output is correct
4 Correct 162 ms 49488 KB Output is correct
5 Correct 144 ms 48416 KB Output is correct
6 Correct 17 ms 20448 KB Output is correct
7 Correct 17 ms 20416 KB Output is correct
8 Correct 19 ms 20364 KB Output is correct
9 Correct 155 ms 47616 KB Output is correct
10 Correct 163 ms 47452 KB Output is correct
11 Correct 170 ms 47620 KB Output is correct
12 Correct 182 ms 46148 KB Output is correct
13 Correct 138 ms 46772 KB Output is correct
14 Incorrect 16 ms 19916 KB Output isn't correct
15 Halted 0 ms 0 KB -