結果

問題 No.898 tri-βutree
ユーザー polylogKpolylogK
提出日時 2019-09-17 14:49:00
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 9,364 bytes
コンパイル時間 3,128 ms
コンパイル使用メモリ 211,708 KB
実行使用メモリ 33,696 KB
最終ジャッジ日時 2024-10-03 05:14:35
合計ジャッジ時間 46,386 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 475 ms
33,696 KB
testcase_01 WA -
testcase_02 WA -
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 -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std::literals::string_literals;
using i64 = long long;
using std::cout;
using std::endl;
using std::cin;

template<typename T>
std::vector<T> make_v(size_t a){return std::vector<T>(a);}

template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
  return std::vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}

// build: you have to run it before you use
// for_each: process [l, r]
// for_each_edge: process [l, r]
// distance: returns the dist (l, r)
class heavy_light_decomposition {
	using size_type = size_t;

	using F = std::function<void (int, int)>;

	public:
	std::vector<std::vector<int>> g;
	std::vector<int> vid, inv;

	private:
	std::vector<int> head, sz, heavy, par, dep, type;

	void dfs(int root) {
		using P = std::pair<int, int>;
		
		par[root] = -1;
		dep[root] = 0;
		std::stack<P> st;
		st.push({root, 0});
		while(!st.empty()) {
			int v = st.top().first;
			int & i = st.top().second;
		
			if(i < g[v].size()) {
				int u = g[v][i++];
				if(u == par[v]) continue;
				par[u] = v;
				dep[u] = dep[v] + 1;
				st.push({u, 0});
			} else {
				st.pop();
				int tmp = 0;
				for(auto e: g[v]) {
					if(e == par[v]) continue;
					sz[v] += sz[e];
					if(tmp < sz[e]) {
						tmp = sz[e];
						heavy[v] = e;
					}
				}
			}
		}
	}
	void bfs(int root, int c, int & k) {
		std::queue<int> qu({root});
		while(!qu.empty()) {
			int h = qu.front(); qu.pop();

			for(int v = h; v != -1; v = heavy[v]) {
				type[v] = c;
				vid[v] = k++;
				inv[vid[v]] = v;
				head[v] = h;
				for(int e: g[v])
					if(e != par[v] and e != heavy[v]) qu.push(e);
			}
		}
	}

	public:
	heavy_light_decomposition() {}
	heavy_light_decomposition(int n) :
		g(n), vid(n, -1), head(n), sz(n, 1), heavy(n, -1),
		par(n), dep(n), inv(n), type(n) {}
	void add_edge(int a, int b) {
		g[a].push_back(b);
		g[b].push_back(a);
	}
	void build(std::vector<int> rs = std::vector<int>(1, 0)) {
		int c = 0, k = 0;
		for(int r: rs) {
			dfs(r);
			bfs(r, c++, k);
		}
	}
	int lca(int u, int v) {
		while(true) {
			if(vid[u] > vid[v]) std::swap(u, v);
			if(head[u] == head[v]) return u;
			v = par[head[v]];
		}
	}
	void for_each(int u, int v, const F & f) {
		while(true) {
			if(vid[u] > vid[v]) std::swap(u, v);
			f(std::max(vid[head[v]], vid[u]), vid[v]);
			if(head[u] != head[v]) v = par[head[v]];
			else break;
		}
	}
	void for_each_edge(int u, int v, const F & f) {
		while(true) {
			if(vid[u] > vid[v]) std::swap(u, v);
			if(head[u] != head[v]) {
				f(vid[head[v]], vid[v]);
				v = par[head[v]];
			} else {
				if(u != v) f(vid[u] + 1, vid[v]);
				break;
			}
		}
	}

	int distance(int u, int v) {
		return dep[u] + dep[v] - 2 * dep[lca(u, v)];
	}
};

template<typename Monoid, typename OperatorMonoid = Monoid>
class lazy_segment_tree {
	using value_type = Monoid;
	using operator_type = OperatorMonoid;
	using size_type = size_t;

	using F = std::function<value_type (value_type, value_type)>;
	using G = std::function<value_type (value_type, operator_type, int, int)>;
	using H = std::function<operator_type (operator_type, operator_type)>;
	
	size_type size_;
	size_type height_;

	F f;
	G g;
	H h;
	value_type id;
	operator_type id_op;
	std::vector<value_type> data;
	std::vector<operator_type> lazy;
	std::vector<size_type> depth;
	
	const size_type get_height(const size_type& size) const {
		size_type height = 1;
		while(1 << height < size) height++;
		return height;
	}
	const size_type base_size() const {
		return 1 << height_;
	}
	const value_type reflect(const size_type & k) {
		if(lazy[k] == id_op) return data[k];
		int l = (k - (1 << depth[k])) * (base_size() >> depth[k]);
		int r = l + (base_size() >> depth[k]);
		return g(data[k], lazy[k], l, r);
	}
	void eval(const size_type & k) {
		if(lazy[k] == id_op) return;
		if(k < base_size()) {
			lazy[k << 1 ^ 0] = h(lazy[k << 1 ^ 0], lazy[k]);
			lazy[k << 1 ^ 1] = h(lazy[k << 1 ^ 1], lazy[k]);
		}
		data[k] = reflect(k);
		lazy[k] = id_op;
	}
	void thrust(const size_type & k) {
		for(int i = height_; i >= 0; i--) eval(k >> i);
	}
	void recalc(size_type k) {
		while(k >>= 1) data[k] = f(reflect(k << 1 ^ 0), reflect(k << 1 ^ 1));
	}
	
	public:
	lazy_segment_tree() {}
	lazy_segment_tree(int n, const F & f, const G & g, const H & h, const value_type & id, const operator_type & id_op) :
		size_(n), f(f), g(g), h(h), id(id), id_op(id_op) {
		height_ = get_height(size_);
		data.assign(base_size() << 1, id);
		lazy.assign(base_size() << 1, id_op);
		depth.assign(base_size() << 1, 0);
		for(int i = 0; i < height_ + 1; i++)
			for(int j = (1 << i); j < (1 << (i + 1)); j++)
				depth[j] = i;
	}
	void update(size_type a, size_type b, operator_type x) {
		thrust(a += base_size());
		thrust(b += base_size() - 1);
		for(size_type l = a, r = b + 1; l < r; l >>= 1, r >>= 1) {
			if(l & 1) lazy[l] = h(lazy[l++], x);
			if(r & 1) lazy[--r] = h(lazy[r], x);
		}
		recalc(a);
		recalc(b);
	}
	void change(size_type k, const value_type x) {
		thrust(k += base_size());
		data[k] = x;
		lazy[k] = id_op;
		recalc(k);
	}
	const value_type fold(size_type a, size_type b) {
		thrust(a += base_size());
		thrust(b += base_size() - 1);

		value_type left_value = id;
		value_type right_value = id;
		for(size_type l = a, r = b + 1; l < r; l >>= 1, r >>= 1) {
			if(l & 1) left_value = f(left_value, reflect(l++));
			if(r & 1) right_value = f(reflect(--r), right_value);
		}
		return f(left_value, right_value);
	}

	const value_type operator[](const size_type & k) {
		return fold(k, k + 1);
	}
};

struct node {
	int used;
	int depth;
	int label;
	int depth_all;
	int label_all;
	
	node() : used(1), depth(-1), label(-1), depth_all(-1), label_all(-1) {}
	node(int used, int depth, int label, int depth_all, int label_all) : used(used), depth(depth), label(label), depth_all(depth_all), label_all(label_all) {}
	void print() {
		printf("used		= %d\n", used);
		printf("depth 		= %d\n", depth);
		printf("label 		= %d\n", label);
		printf("depth_all 	= %d\n", depth_all);
		printf("label_all	= %d\n", label_all);
	}
};

int main() {
	int n; scanf("%d", &n);

	std::vector<std::vector<std::pair<int, i64>>> g(n);
	heavy_light_decomposition hld(n);
	for(int i = 0; i < n - 1; i++) {
		int a, b, c; scanf("%d%d%d", &a, &b, &c);

		g[a].push_back({b, c});
		g[b].push_back({a, c});
		hld.add_edge(a, b);
	}
	hld.build();

	std::vector<i64> dist(n), depth(n);
	auto dfs = [&](auto && dfs, int v, int par) -> void {
		for(auto e: g[v]) {
			if(e.first == par) continue;
			dist[e.first] = dist[v] + e.second;
			depth[e.first] = depth[v] + 1;
			dfs(dfs, e.first, v);
		}
	};
	dfs(dfs, 0, -1);
	
	auto calc = [dist, &hld](int u, int v) {
		return dist[u] + dist[v] - 2LL * dist[hld.lca(u, v)];
	};

	auto f = [](node a, node b) {
		node ret;
		ret.used = 0;
		if(a.depth_all > b.depth_all) {
			ret.label_all = a.label_all;
			ret.depth_all = a.depth_all;
		} else {
			ret.label_all = b.label_all;
			ret.depth_all = b.depth_all;
		}

		if(a.used and b.used) {
			ret.used = 1;
			ret.label = ret.label_all;
			ret.depth = ret.depth_all;
			return ret;
		} else if(a.used and !b.used) {
			if(a.depth_all > b.depth) {
				ret.label = a.label_all;
				ret.depth = a.depth_all;
			} else {
				ret.label = b.label;
				ret.depth = b.depth;
			}
		} else if(!a.used and b.used) {
			if(a.depth > b.depth_all) {
				ret.label = a.label;
				ret.depth = a.depth;
			} else {
				ret.label = b.label_all;
				ret.depth = b.depth_all;
			}
		} else {
			if(a.depth > b.depth) {
				ret.label = a.label;
				ret.depth = a.depth;
			} else {
				ret.label = b.label;
				ret.depth = b.depth;
			}
		}
		return ret;
	};
	auto gg = [](node a, int b, int l, int r) {
		if(b) {
			a.used = 1;
			a.depth = a.depth_all;
			a.label = a.label_all;
		} else {
			a.used = 0;
			a.depth = -1;
			a.label = -1;
		}
		return a;
	};
	auto h = [](int a, int b) { return b; };
	
	lazy_segment_tree<node, int> A(n, f, gg, h, node(), -1);
	for(int i = 0; i < n; i++) {
		int v = hld.inv[i];

		A.change(i, node(0, -1, -1, depth[v], v));
	}
	auto kiri = [&A](int l, int r) {
		A.update(l, r + 1, 1);
	};
	auto irik = [&A](int l, int r) {
		A.update(l, r + 1, 0);
	};

	int q; scanf("%d", &q);
	while(q--) {
		int k = 3; // scanf("%d", &k);
		std::vector<std::pair<int, int>> vec;
		for(int i = 0; i < k; i++) {
			int x; scanf("%d", &x);

			vec.push_back({x, depth[x]});
		}
		sort(begin(vec), end(vec));

		if(k == 1) {
			printf("0\n");
			continue;
		}

		std::vector<std::pair<int, int>> edge(1, {vec[0].first, vec[1].first});
		i64 ans = calc(vec[0].first, vec[1].first);
		int c = hld.lca(vec[0].first, vec[1].first);
		hld.for_each(vec[0].first, vec[1].first, kiri);
		
		for(int i = 2; i < vec.size(); i++) {
			int v = vec[i].first;
			
			node tmp = node();
			auto tanpo = [&](int l, int r) {
				tmp = f(tmp, A.fold(l, r + 1));
			};
			hld.for_each(0, v, tanpo);

			if(tmp.depth == -1) {
				int u = hld.lca(v, c);
				ans += calc(u,  v) + calc(u, c);
				hld.for_each(u, v, kiri);
				hld.for_each(u, c, kiri);
				c = hld.lca(u, v);

				edge.push_back({u, v});
				edge.push_back({u, c});
			} else {
				int u = tmp.label;
				ans += calc(u, v);
				hld.for_each(u, v, kiri);

				edge.push_back({u, v});
			}
		}

		for(auto e: edge) {
			int u = e.first, v = e.second;

			hld.for_each(u, v, irik);
		}

		printf("%lld\n", ans);
	}
	return 0;
}
0