結果

問題 No.1197 モンスターショー
ユーザー square1001square1001
提出日時 2020-08-22 15:07:41
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
RE  
実行時間 -
コード長 4,626 bytes
コンパイル時間 1,239 ms
コンパイル使用メモリ 92,916 KB
実行使用メモリ 34,304 KB
最終ジャッジ日時 2024-10-15 09:24:53
合計ジャッジ時間 5,183 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 RE -
testcase_01 RE -
testcase_02 RE -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 WA -
testcase_32 WA -
testcase_33 WA -
testcase_34 WA -
testcase_35 WA -
testcase_36 WA -
testcase_37 WA -
testcase_38 WA -
testcase_39 WA -
testcase_40 WA -
testcase_41 WA -
testcase_42 WA -
権限があれば一括ダウンロードができます

ソースコード

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), 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 = 0;
	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)) {
					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)) {
					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;
	};
	cout << par[bits - 1][N - 1] << endl;
	return 0;
	// 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