답안 #469384

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
469384 2021-08-31T17:27:39 Z sinamhdv Sumtree (INOI20_sumtree) C++11
100 / 100
1538 ms 68676 KB
// INOI20_sumtree
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod = 1000 * 1000 * 1000 + 7;
const int INF = 1e9 + 100;
const ll LINF = 1e18 + 100;

#ifdef DEBUG
#define dbg(x) cout << #x << " = " << (x) << endl << flush;
#define dbgr(s, f) { cout << #s << ": "; for (auto _ = (s); _ != (f); _++) cout << *_ << ' '; cout << endl << flush; }
#else
#define dbg(x) ;
#define dbgr(s, f) ;
#endif
#define fast_io ios::sync_with_stdio(0); cin.tie(0);
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define fr first
#define sc second
#define endl '\n'

const int MAXN = 200100;
const int MAXF = 500100;
const int LOGN = 25;

inline int poww(int a, int b)
{
	int res = 1;
	for (; b; a = (ll)a * a % mod, b /= 2) if (b & 1) res = (ll)res * a % mod;
	return res;
}

int n, rt, q;
vector<int> adj[MAXN];
int bad, ans;
int sttime[MAXN], fntime[MAXN], timer, h[MAXN];
int lbl[MAXN], val[MAXN], cnt[MAXN];
int lpar[LOGN][MAXN];
int fact[MAXF], finv[MAXF];

inline int comb(int n, int k)
{
	return (fact[n] * (ll)finv[k] % mod) * finv[n - k] % mod;
}

void dfs1(int v)
{
	sttime[v] = timer++;
	for (int u : adj[v]) if (u != lpar[0][v])
	{
		lpar[0][u] = v;
		h[u] = h[v] + 1, dfs1(u);
	}
	fntime[v] = timer;
}

struct FEN
{
	ll fen[MAXN];

	inline void addind(int i, ll x)
	{
		for (i++; i < MAXN; i += i & -i) fen[i] += x;
	}

	inline ll pget(int i)
	{
		ll res = 0;
		for (i++; i > 0; i -= i & -i) res += fen[i];
		return res;
	}

	inline ll get(int l, int r)
	{
		if (l > r) return 0;
		return pget(r) - pget(l - 1);
	}

	inline void add(int l, int r, ll x)
	{
		addind(l, x);
		addind(r + 1, -x);
	}

} valfen, ancfen;

struct node
{
	int mn, mincnt, lz;
};

struct SEG
{
	node seg[4 * MAXN];

	inline node mrg(const node &lc, const node &rc)
	{
		node res = {0, 0, -1};
		res.mn = min(lc.mn, rc.mn);
		res.mincnt = 0;
		if (lc.mn == res.mn) res.mincnt += lc.mincnt;
		if (rc.mn == res.mn) res.mincnt += rc.mincnt;
		return res;
	}

	inline void pushdown(int v)
	{
		if (seg[v].lz == -1) return;
		int mn = min(seg[2 * v].mn, seg[2 * v + 1].mn);
		FOR(t, 2 * v, 2 * v + 2)
		{
			if (seg[t].mn == mn) seg[t].mn = seg[t].lz = seg[v].lz;
		}
		seg[v].lz = -1;
	}

	void build(int v = 1, int l = 0, int r = n - 1)
	{
		if (l == r)
		{
			seg[v] = {0, 1, -1};
			return;
		}
		int mid = (r + l) / 2;
		build(2 * v, l, mid);
		build(2 * v + 1, mid + 1, r);
		seg[v] = mrg(seg[2 * v], seg[2 * v + 1]);
		seg[v].lz = -1;
	}

	void rset(int L, int R, int x, int mn, int v = 1, int l = 0, int r = n - 1)
	{
		if (l > R || r < L || seg[v].mn > mn) return;
		if (l >= L && r <= R && seg[v].mn == mn)
		{
			seg[v].mn = seg[v].lz = x;
			return;
		}
		int mid = (r + l) / 2;
		pushdown(v);
		rset(L, R, x, mn, 2 * v, l, mid);
		rset(L, R, x, mn, 2 * v + 1, mid + 1, r);
		seg[v] = mrg(seg[2 * v], seg[2 * v + 1]);
	}

	node getmin(int L, int R, int v = 1, int l = 0, int r = n - 1)
	{
		if (l > R || r < L) return {INF, 0, 0};
		if (l >= L && r <= R) return seg[v];
		int mid = (r + l) / 2;
		pushdown(v);
		return mrg(getmin(L, R, 2 * v, l, mid), getmin(L, R, 2 * v + 1, mid + 1, r));
	}

} seg;

inline int getpar(int x, int d)
{
	FOR(i, 0, LOGN) if (d >> i & 1) x = lpar[i][x];
	return x;
}

inline void addans(int i)
{
	if (val[i] < 0) bad++;
	else ans = (ll)ans * comb(val[i] + cnt[i] - 1, cnt[i] - 1) % mod;
}

inline void remans(int i)
{
	if (val[i] < 0) bad--;
	else ans = (ll)ans * poww(comb(val[i] + cnt[i] - 1, cnt[i] - 1), mod - 2) % mod;
}

inline void updateval(int v)
{
	ll nw = lbl[v] - valfen.get(sttime[v] + 1, fntime[v] - 1);
	valfen.addind(sttime[v], nw - val[v]);
	val[v] = nw;
}

inline int findanc(int v)
{
	int l = 0, r = h[v] + 1;
	int cur = ancfen.pget(sttime[v]);
	while (r - l > 1)
	{
		int mid = (r + l) / 2;
		int x = getpar(v, mid);
		if (ancfen.pget(sttime[x]) == cur) l = mid;
		else r = mid;
	}
	return getpar(v, l);
}

int32_t main(void)
{
	fast_io;

	fact[0] = 1;
	FOR(i, 1, MAXF) fact[i] = fact[i - 1] * (ll)i % mod;
	finv[MAXF - 1] = poww(fact[MAXF - 1], mod - 2);
	for (int i = MAXF - 2; i >= 0; i--) finv[i] = (ll)finv[i + 1] * (i + 1) % mod;

	cin >> n >> rt;
	FOR(i, 0, n - 1)
	{
		int x, y;
		cin >> x >> y;
		adj[x].pb(y);
		adj[y].pb(x);
	}

	dfs1(1);

	FOR(i, 1, LOGN) FOR(j, 1, n + 1) lpar[i][j] = lpar[i - 1][lpar[i - 1][j]];

	ans = comb(n + rt - 1, n - 1);
	cout << ans << endl;
	ancfen.add(0, n - 1, 1);
	lbl[1] = val[1] = rt;
	cnt[1] = n;
	seg.build();

	cin >> q;
	while (q--)
	{
		int op, v;
		cin >> op >> v;
		if (op == 1)	// add
		{
			int x;
			cin >> x;
			lbl[v] = x;

			// update anc
			int l = findanc(v);
			ancfen.add(sttime[v], fntime[v] - 1, 1);

			remans(l);

			// update cnt
			node p = seg.getmin(sttime[v], fntime[v] - 1);
			seg.rset(sttime[v], fntime[v] - 1, sttime[v], p.mn);
			cnt[l] -= p.mincnt;
			cnt[v] += p.mincnt;

			// update val
			updateval(v);
			updateval(l);

			addans(v);
			addans(l);
		}
		else	// rem
		{
			ancfen.add(sttime[v], fntime[v] - 1, -1);
			int l = findanc(v);

			remans(l);
			remans(v);

			node p = seg.getmin(sttime[v], fntime[v] - 1);
			seg.rset(sttime[v], fntime[v] - 1, sttime[l], p.mn);
			cnt[l] += p.mincnt;
			cnt[v] = 0;

			valfen.addind(sttime[v], -val[v]);
			lbl[v] = val[v] = 0;
			updateval(l);

			addans(l);
		}

		ans = (mod + ans % mod) % mod;
		if (bad) cout << "0\n";
		else cout << ans << endl;
	}

	return 0;
}


# 결과 실행 시간 메모리 Grader output
1 Correct 156 ms 49732 KB Output is correct
2 Correct 153 ms 49800 KB Output is correct
3 Correct 191 ms 49776 KB Output is correct
4 Correct 159 ms 49860 KB Output is correct
5 Correct 145 ms 46584 KB Output is correct
6 Correct 13 ms 9788 KB Output is correct
7 Correct 14 ms 9604 KB Output is correct
8 Correct 13 ms 9672 KB Output is correct
9 Correct 165 ms 43740 KB Output is correct
10 Correct 156 ms 43616 KB Output is correct
11 Correct 160 ms 43728 KB Output is correct
12 Correct 149 ms 42308 KB Output is correct
13 Correct 147 ms 47044 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 9164 KB Output is correct
2 Correct 12 ms 9204 KB Output is correct
3 Correct 12 ms 9164 KB Output is correct
4 Correct 12 ms 9164 KB Output is correct
5 Correct 14 ms 9204 KB Output is correct
6 Correct 17 ms 9604 KB Output is correct
7 Correct 17 ms 9548 KB Output is correct
8 Correct 17 ms 9548 KB Output is correct
9 Correct 19 ms 9804 KB Output is correct
10 Correct 20 ms 9916 KB Output is correct
11 Correct 23 ms 9944 KB Output is correct
12 Correct 14 ms 9804 KB Output is correct
13 Correct 20 ms 9876 KB Output is correct
14 Correct 21 ms 9848 KB Output is correct
15 Correct 20 ms 9932 KB Output is correct
16 Correct 19 ms 9804 KB Output is correct
17 Correct 20 ms 9848 KB Output is correct
18 Correct 18 ms 9484 KB Output is correct
19 Correct 19 ms 9804 KB Output is correct
20 Correct 16 ms 9548 KB Output is correct
21 Correct 16 ms 9500 KB Output is correct
22 Correct 13 ms 9204 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 224 ms 54640 KB Output is correct
2 Correct 285 ms 55740 KB Output is correct
3 Correct 240 ms 57540 KB Output is correct
4 Correct 416 ms 58412 KB Output is correct
5 Correct 800 ms 56804 KB Output is correct
6 Correct 16 ms 9932 KB Output is correct
7 Correct 14 ms 9720 KB Output is correct
8 Correct 18 ms 9724 KB Output is correct
9 Correct 527 ms 53392 KB Output is correct
10 Correct 453 ms 52932 KB Output is correct
11 Correct 405 ms 52708 KB Output is correct
12 Correct 433 ms 52828 KB Output is correct
13 Correct 762 ms 67724 KB Output is correct
14 Correct 755 ms 68624 KB Output is correct
15 Correct 742 ms 68676 KB Output is correct
16 Correct 747 ms 68676 KB Output is correct
17 Correct 745 ms 68660 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 853 ms 51264 KB Output is correct
2 Correct 853 ms 53352 KB Output is correct
3 Correct 827 ms 53432 KB Output is correct
4 Correct 856 ms 53236 KB Output is correct
5 Correct 803 ms 51564 KB Output is correct
6 Correct 829 ms 53308 KB Output is correct
7 Correct 655 ms 33372 KB Output is correct
8 Correct 700 ms 33360 KB Output is correct
9 Correct 907 ms 53384 KB Output is correct
10 Correct 801 ms 53184 KB Output is correct
11 Correct 804 ms 53400 KB Output is correct
12 Correct 661 ms 33344 KB Output is correct
13 Correct 427 ms 29748 KB Output is correct
14 Correct 532 ms 31692 KB Output is correct
15 Correct 562 ms 31776 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 156 ms 49732 KB Output is correct
2 Correct 153 ms 49800 KB Output is correct
3 Correct 191 ms 49776 KB Output is correct
4 Correct 159 ms 49860 KB Output is correct
5 Correct 145 ms 46584 KB Output is correct
6 Correct 13 ms 9788 KB Output is correct
7 Correct 14 ms 9604 KB Output is correct
8 Correct 13 ms 9672 KB Output is correct
9 Correct 165 ms 43740 KB Output is correct
10 Correct 156 ms 43616 KB Output is correct
11 Correct 160 ms 43728 KB Output is correct
12 Correct 149 ms 42308 KB Output is correct
13 Correct 147 ms 47044 KB Output is correct
14 Correct 12 ms 9164 KB Output is correct
15 Correct 12 ms 9204 KB Output is correct
16 Correct 12 ms 9164 KB Output is correct
17 Correct 12 ms 9164 KB Output is correct
18 Correct 14 ms 9204 KB Output is correct
19 Correct 17 ms 9604 KB Output is correct
20 Correct 17 ms 9548 KB Output is correct
21 Correct 17 ms 9548 KB Output is correct
22 Correct 19 ms 9804 KB Output is correct
23 Correct 20 ms 9916 KB Output is correct
24 Correct 23 ms 9944 KB Output is correct
25 Correct 14 ms 9804 KB Output is correct
26 Correct 20 ms 9876 KB Output is correct
27 Correct 21 ms 9848 KB Output is correct
28 Correct 20 ms 9932 KB Output is correct
29 Correct 19 ms 9804 KB Output is correct
30 Correct 20 ms 9848 KB Output is correct
31 Correct 18 ms 9484 KB Output is correct
32 Correct 19 ms 9804 KB Output is correct
33 Correct 16 ms 9548 KB Output is correct
34 Correct 16 ms 9500 KB Output is correct
35 Correct 13 ms 9204 KB Output is correct
36 Correct 224 ms 54640 KB Output is correct
37 Correct 285 ms 55740 KB Output is correct
38 Correct 240 ms 57540 KB Output is correct
39 Correct 416 ms 58412 KB Output is correct
40 Correct 800 ms 56804 KB Output is correct
41 Correct 16 ms 9932 KB Output is correct
42 Correct 14 ms 9720 KB Output is correct
43 Correct 18 ms 9724 KB Output is correct
44 Correct 527 ms 53392 KB Output is correct
45 Correct 453 ms 52932 KB Output is correct
46 Correct 405 ms 52708 KB Output is correct
47 Correct 433 ms 52828 KB Output is correct
48 Correct 762 ms 67724 KB Output is correct
49 Correct 755 ms 68624 KB Output is correct
50 Correct 742 ms 68676 KB Output is correct
51 Correct 747 ms 68676 KB Output is correct
52 Correct 745 ms 68660 KB Output is correct
53 Correct 853 ms 51264 KB Output is correct
54 Correct 853 ms 53352 KB Output is correct
55 Correct 827 ms 53432 KB Output is correct
56 Correct 856 ms 53236 KB Output is correct
57 Correct 803 ms 51564 KB Output is correct
58 Correct 829 ms 53308 KB Output is correct
59 Correct 655 ms 33372 KB Output is correct
60 Correct 700 ms 33360 KB Output is correct
61 Correct 907 ms 53384 KB Output is correct
62 Correct 801 ms 53184 KB Output is correct
63 Correct 804 ms 53400 KB Output is correct
64 Correct 661 ms 33344 KB Output is correct
65 Correct 427 ms 29748 KB Output is correct
66 Correct 532 ms 31692 KB Output is correct
67 Correct 562 ms 31776 KB Output is correct
68 Correct 12 ms 9192 KB Output is correct
69 Correct 13 ms 9164 KB Output is correct
70 Correct 1481 ms 61720 KB Output is correct
71 Correct 1474 ms 61648 KB Output is correct
72 Correct 1503 ms 61600 KB Output is correct
73 Correct 1495 ms 61704 KB Output is correct
74 Correct 1533 ms 61416 KB Output is correct
75 Correct 1538 ms 58560 KB Output is correct
76 Correct 702 ms 55364 KB Output is correct
77 Correct 768 ms 55212 KB Output is correct
78 Correct 839 ms 54212 KB Output is correct
79 Correct 1376 ms 58592 KB Output is correct
80 Correct 1338 ms 56744 KB Output is correct
81 Correct 1381 ms 58084 KB Output is correct
82 Correct 536 ms 51156 KB Output is correct
83 Correct 841 ms 56012 KB Output is correct
84 Correct 974 ms 55412 KB Output is correct
85 Correct 923 ms 55324 KB Output is correct