結果

問題 No.1094 木登り / Climbing tree
ユーザー tkmst201tkmst201
提出日時 2021-03-11 12:30:09
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 689 ms / 2,000 ms
コード長 5,352 bytes
コンパイル時間 1,537 ms
コンパイル使用メモリ 89,096 KB
実行使用メモリ 39,888 KB
最終ジャッジ日時 2024-11-08 07:16:54
合計ジャッジ時間 17,204 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 648 ms
39,756 KB
testcase_02 AC 133 ms
39,680 KB
testcase_03 AC 61 ms
5,248 KB
testcase_04 AC 141 ms
18,612 KB
testcase_05 AC 303 ms
34,844 KB
testcase_06 AC 230 ms
13,952 KB
testcase_07 AC 666 ms
39,884 KB
testcase_08 AC 633 ms
39,888 KB
testcase_09 AC 614 ms
39,884 KB
testcase_10 AC 689 ms
39,856 KB
testcase_11 AC 682 ms
39,764 KB
testcase_12 AC 615 ms
39,756 KB
testcase_13 AC 598 ms
39,752 KB
testcase_14 AC 610 ms
39,756 KB
testcase_15 AC 166 ms
10,624 KB
testcase_16 AC 359 ms
30,976 KB
testcase_17 AC 263 ms
19,328 KB
testcase_18 AC 217 ms
14,976 KB
testcase_19 AC 318 ms
25,984 KB
testcase_20 AC 603 ms
39,760 KB
testcase_21 AC 285 ms
20,352 KB
testcase_22 AC 592 ms
39,756 KB
testcase_23 AC 595 ms
39,760 KB
testcase_24 AC 607 ms
39,752 KB
testcase_25 AC 616 ms
39,760 KB
testcase_26 AC 625 ms
39,752 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <vector>
#include <cassert>
#include <stack>
#include <utility>

template<bool EDGE = true>
struct EulerTour {
	using size_type = std::size_t;
	using Graph = std::vector<std::vector<int>>;
	
private:
	int n, root;
	std::vector<int> in_, out_, par_, g_idx;
	
public:
	EulerTour(const Graph & g, int root = 0)
		: n(g.size()), root(root), in_(size(), -1), out_(size(), -1), par_(n, -1), g_idx(n << 1, -1) {
		std::stack<std::pair<int, int>> stk;
		int num = 0;
		in_[root] = num++;
		stk.emplace(root, 0);
		while (!stk.empty()) {
			auto [u, i] = stk.top();
			stk.pop();
			if (i < g[u].size()) {
				const int v = g[u][i];
				stk.emplace(u, i + 1);
				if (v == par_[u]) g_idx[u << 1 | 1] = i;
				else {
					in_[v] = num++;
					par_[v] = u;
					g_idx[v << 1] = i;
					stk.emplace(v, 0);
				}
			}
			else {
				out_[u] = num;
				if (EDGE) ++num;
			}
		}
	}
	
	size_type size() const noexcept {
		return EDGE ? n << 1 : n;
	}
	
	int par(int k) const noexcept {
		assert(0 <= k && k < n);
		return par_[k];
	}
	
	int in(int k) const noexcept {
		assert(0 <= k && k < n);
		return in_[k];
	}
	
	int out(int k) const noexcept {
		assert(0 <= k && k < n);
		return out_[k];
	}
	
	std::pair<int, int> par_from(int k) const noexcept {
		assert(0 <= k && k < n);
		return {par_[k], g_idx[k << 1]};
	}
	
	int par_to(int k) const noexcept {
		assert(0 <= k && k < n);
		return g_idx[k << 1 | 1];
	}
};

#include <vector>
#include <cassert>
#include <functional>

/**
 * @brief https://tkmst201.github.io/Library/DataStructure/BinaryIndexedTree.hpp
 */
template<typename T>
struct BinaryIndexedTree {
	using value_type = T;
	using const_reference = const value_type &;
	using F = std::function<value_type (const_reference, const_reference)>;
	using size_type = std::size_t;
	
private:
	size_type n;
	value_type id_elem;
	F f;
	std::vector<value_type> node;
	
public:
	BinaryIndexedTree(size_type n, const_reference id_elem, const F & f)
		: n(n), id_elem(id_elem), f(f), node(n + 1, id_elem) {}
	
	size_type size() const noexcept {
		return n;
	}
	
	void add(size_type i, const_reference x) noexcept {
		assert(i < size());
		++i;
		for (; i <= size(); i += i & -i) node[i] = f(node[i], x);
	}
	
	value_type sum(size_type i) const noexcept {
		assert(i <= size());
		value_type res = id_elem;
		for (; i > 0; i -= i & -i) res = f(node[i], res);
		return res;
	}
	
	size_type lower_bound(const_reference x) const noexcept {
		size_type res = 0;
		size_type s = id_elem, w = 1;
		while (w < size()) w <<= 1;
		for (; w > 0; w >>= 1) {
			if (res + w <= size()) {
				value_type cur = f(s, node[res + w]);
				if (cur < x) {
					res += w;
					s = cur;
				}
			}
		}
		return res;
	}
};

/**
 * @brief https://tkmst201.github.io/Library/GraphTheory/LowestCommonAncestor.hpp
 */
struct LowestCommonAncestor {
	using size_type = std::size_t;
	using Graph = std::vector<std::vector<int>>;
	
private:
	int n, logn;
	std::vector<std::vector<int>> par;
	std::vector<int> depth_;
	
public:
	LowestCommonAncestor(const Graph & g, int root = 0) : n(g.size()) {
		assert(0 <= root && root < size());
		logn = 1;
		while ((1 << logn) + 1 <= size()) ++logn;
		par.assign(logn, std::vector<int>(size()));
		depth_.assign(size(), 0);
		std::stack<std::pair<int, int>> stk;
		par[0][root] = root;
		stk.emplace(root, root);
		while (!stk.empty()) {
			auto [u, p] = stk.top();
			stk.pop();
			for (int v : g[u]) {
				if (v == p) continue;
				assert(0 <= v && v < size());
				par[0][v] = u;
				depth_[v] = depth_[u] + 1;
				stk.emplace(v, u);
			}
		}
		for (int i = 1; i < logn; ++i) {
			for (int j = 0; j < size(); ++j) par[i][j] = par[i - 1][par[i - 1][j]];
		}
	}
	
	size_type size() const noexcept {
		return n;
	}
	
	int find(int a, int b) const noexcept {
		assert(0 <= a && a < size());
		assert(0 <= b && b < size());
		assert(par[0][a] != size());
		assert(par[0][b] != size());
		if (depth_[a] < depth_[b]) std::swap(a, b);
		a = parent(a, depth_[a] - depth_[b]);
		if (a == b) return a;
		for (int i = logn - 1; i >= 0; --i) {
			if (par[i][a] != par[i][b]) a = par[i][a], b = par[i][b]; 
		}
		return par[0][a];
	}
	
	int parent(int u, int k = 1) const noexcept {
		assert(0 <= u && u < size());
		assert(k <= depth_[u]);
		assert(par[0][u] != size());
		for (int i = 0; i < logn; ++i) if (k >> i & 1) u = par[i][u];
		return u;
	}
	
	int depth(int u) const noexcept {
		assert(0 <= u && u < size());
		assert(par[0][u] != size());
		return depth_[u];
	}
};

#include <cstdio>
#include <utility>

int main() {
	int N;
	scanf("%d", &N);
	
	EulerTour<true>::Graph g(N);
	std::vector<int> A(N - 1), B(N - 1), C(N - 1);
	for (int i = 0; i < N - 1; ++i) {
		scanf("%d %d %d", &A[i], &B[i], &C[i]);
		--A[i]; --B[i];
		g[A[i]].emplace_back(B[i]);
		g[B[i]].emplace_back(A[i]);
	}
	EulerTour<true> et(g);
	
	using ll = long long;
	BinaryIndexedTree<ll> bit(et.size(), 0, [](auto x, auto y) { return x + y; });
	for (int i = 0; i < N - 1; ++i) {
		if (et.par(A[i]) != B[i]) std::swap(A[i], B[i]);
		bit.add(et.in(A[i]), C[i]);
		bit.add(et.out(A[i]), -C[i]);
	}
	LowestCommonAncestor lca(g);
	
	int Q;
	scanf("%d", &Q);
	while (Q--) {
		int s, t;
		scanf("%d %d", &s, &t);
		--s; --t;
		const int l = lca.find(s, t);
		auto func = [&](int a) {
			return bit.sum(et.in(a) + 1) - bit.sum(et.in(l) + 1);
		};
		printf("%lld\n", func(s) + func(t));
	}
}
0