結果

問題 No.1197 モンスターショー
ユーザー square1001square1001
提出日時 2020-08-22 15:14:54
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 344 ms / 3,000 ms
コード長 4,601 bytes
コンパイル時間 1,589 ms
コンパイル使用メモリ 93,940 KB
実行使用メモリ 34,176 KB
最終ジャッジ日時 2024-10-15 18:32:20
合計ジャッジ時間 10,706 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 AC 3 ms
5,248 KB
testcase_04 AC 2 ms
5,248 KB
testcase_05 AC 2 ms
5,248 KB
testcase_06 AC 2 ms
5,248 KB
testcase_07 AC 78 ms
29,312 KB
testcase_08 AC 107 ms
12,416 KB
testcase_09 AC 147 ms
19,904 KB
testcase_10 AC 199 ms
19,428 KB
testcase_11 AC 115 ms
8,576 KB
testcase_12 AC 90 ms
5,888 KB
testcase_13 AC 67 ms
13,568 KB
testcase_14 AC 187 ms
13,824 KB
testcase_15 AC 124 ms
8,064 KB
testcase_16 AC 235 ms
22,436 KB
testcase_17 AC 259 ms
22,836 KB
testcase_18 AC 85 ms
9,344 KB
testcase_19 AC 231 ms
19,388 KB
testcase_20 AC 43 ms
8,192 KB
testcase_21 AC 116 ms
5,248 KB
testcase_22 AC 16 ms
5,248 KB
testcase_23 AC 223 ms
14,788 KB
testcase_24 AC 176 ms
14,500 KB
testcase_25 AC 99 ms
11,136 KB
testcase_26 AC 181 ms
11,392 KB
testcase_27 AC 225 ms
20,976 KB
testcase_28 AC 150 ms
12,400 KB
testcase_29 AC 124 ms
14,172 KB
testcase_30 AC 105 ms
15,860 KB
testcase_31 AC 87 ms
12,928 KB
testcase_32 AC 71 ms
5,248 KB
testcase_33 AC 54 ms
11,008 KB
testcase_34 AC 344 ms
23,760 KB
testcase_35 AC 340 ms
23,752 KB
testcase_36 AC 338 ms
23,884 KB
testcase_37 AC 341 ms
23,880 KB
testcase_38 AC 337 ms
23,792 KB
testcase_39 AC 343 ms
23,776 KB
testcase_40 AC 246 ms
34,176 KB
testcase_41 AC 2 ms
5,248 KB
testcase_42 AC 2 ms
5,248 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#ifndef CLASS_FENWICKTREE
#define CLASS_FENWICKTREE

#include <vector>
#include <cassert>
#include <cstddef>

template <class type>
class fenwick_tree {
private:
	std::size_t n, sz;
	std::vector<type> val;
public:
	fenwick_tree() : n(0), sz(0) {};
	fenwick_tree(std::size_t n_) : n(n_) {
		sz = 1; while (sz < n) sz *= 2;
		val = std::vector<type>(sz + 1);
	}
	template <class InputIterator>
	fenwick_tree(InputIterator first, InputIterator last) : n(last - first) {
		sz = 1; while (sz < n) sz *= 2;
		val = std::vector<type>(sz + 1);
		std::size_t cur = 0;
		for (InputIterator it = first; it != last; ++it) val[++cur] += *it;
		for (std::size_t i = 1; i < sz; ++i) val[i + (i & ~(i - 1))] += val[i];
	}
	void add(std::size_t pos, type delta) {
		for (std::size_t i = pos + 1; i <= sz; i += i & ~(i - 1)) {
			val[i] += delta;
		}
	}
	type getsum(std::size_t r) const {
		assert(0 <= r && r <= n);
		type ans = 0;
		for (std::size_t i = r; i >= 1; i -= i & ~(i - 1)) {
			ans += val[i];
		}
		return ans;
	}
	type getsum(std::size_t l, std::size_t r) const {
		assert(0 <= l && l <= r && r <= n);
		return getsum(r) - getsum(l);
	}
	std::size_t binary_search(type threshold) const {
		std::size_t ans = 0;
		for (std::size_t i = (sz >> 1); i >= 1; i >>= 1) {
			if (threshold >= val[ans + i]) {
				threshold -= val[ans + i];
				ans += i;
			}
		}
		return ans;
	}
};

#endif // CLASS_FENWICKTREE

#include <vector>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	int N, K, Q;
	cin >> N >> K >> Q;
	vector<int> C(K);
	for (int i = 0; i < K; ++i) {
		cin >> C[i]; --C[i];
	}
	vector<vector<int> > G(N);
	for (int i = 0; i < N - 1; ++i) {
		int a, b;
		cin >> a >> b; --a, --b;
		G[a].push_back(b);
		G[b].push_back(a);
	}
	// step #1. build tree
	vector<vector<int> > child(N);
	vector<int> p(N), subtree(N, 1), depth(N);
	function<void(int, int)> build_tree_1 = [&](int pos, int pre) {
		p[pos] = pre;
		for (int i : G[pos]) {
			if (i != pre) {
				child[pos].push_back(i);
				depth[i] = depth[pos] + 1;
				build_tree_1(i, pos);
				subtree[pos] += subtree[i];
			}
		}
		sort(child[pos].begin(), child[pos].end(), [&](int i, int j) { return subtree[i] > subtree[j]; });
	};
	build_tree_1(0, 0);
	int track = 0;
	vector<int> lp(N), rp(N);
	function<void(int, int)> build_tree_2 = [&](int pos, int pre) {
		lp[pos] = track++;
		for (int i : child[pos]) {
			build_tree_2(i, pos);
		}
		rp[pos] = track;
	};
	build_tree_2(0, 0);
	// step #2. prepare for heavy-light decomposition
	int bits = 1;
	while ((1 << bits) < N) ++bits;
	vector<vector<int> > par(bits, vector<int>(N));
	par[0] = p;
	for (int i = 1; i < bits; ++i) {
		for (int j = 0; j < N; ++j) {
			par[i][j] = par[i - 1][par[i - 1][j]];
		}
	}
	fenwick_tree<long long> fen1(N), fen2(N);
	function<void(int, int, long long)> range_add = [&](int l, int r, long long x) {
		fen1.add(l, x);
		fen1.add(r, -x);
		fen2.add(l, -l * x);
		fen2.add(r, r * x);
	};
	function<long long(int, int)> range_sum = [&](int l, int r) {
		return fen1.getsum(r) * r - fen1.getsum(l) * l + fen2.getsum(l, r);
	};
	function<void(int, int)> add = [&](int pos, int val) {
		int cdepth = depth[pos];
		while (true) {
			int nxt = pos, ndepth = cdepth;
			for (int i = bits - 1; i >= 0; --i) {
				if (ndepth >= (1 << i) && lp[par[i][nxt]] == lp[pos] - (cdepth - ndepth + (1 << i))) {
					ndepth -= (1 << i);
					nxt = par[i][nxt];
				}
			}
			range_add(lp[nxt], lp[pos] + 1, val);
			if (nxt == 0) break;
			pos = par[0][nxt];
			cdepth = ndepth - 1;
		}
	};
	function<long long(int)> sum = [&](int pos) {
		int cdepth = depth[pos];
		long long res = 0;
		while (true) {
			int nxt = pos, ndepth = cdepth;
			for (int i = bits - 1; i >= 0; --i) {
				if (ndepth >= (1 << i) && lp[par[i][nxt]] == lp[pos] - (cdepth - ndepth + (1 << i))) {
					ndepth -= (1 << i);
					nxt = par[i][nxt];
				}
			}
			res += range_sum(lp[nxt], lp[pos] + 1);
			if (nxt == 0) break;
			pos = par[0][nxt];
			cdepth = ndepth - 1;
		}
		return res;
	};
	// step #3. solve
	long long basic = 0;
	for (int i = 0; i < K; ++i) {
		add(C[i], 1);
		basic += depth[C[i]];
	}
	long long ans = 0;
	for (int i = 0; i < Q; ++i) {
		int tp;
		cin >> tp;
		if (tp == 1) {
			int x, y;
			cin >> x >> y; --x, --y;
			add(C[x], -1);
			basic -= depth[C[x]];
			C[x] = y;
			add(C[x], 1);
			basic += depth[C[x]];
		}
		else {
			int x;
			cin >> x; --x;
			long long ans = 1LL * depth[x] * K + basic;
			long long res = sum(x) - K;
			ans -= res * 2;
			cout << ans << '\n';
		}
	}
	return 0;
}
0