結果

問題 No.901 K-ary εxtrεεmε
コンテスト
ユーザー QCFium
提出日時 2019-11-24 12:51:31
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 284 ms / 3,000 ms
コード長 1,809 bytes
コンパイル時間 2,228 ms
コンパイル使用メモリ 186,976 KB
実行使用メモリ 28,416 KB
最終ジャッジ日時 2024-10-12 04:17:38
合計ジャッジ時間 9,887 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 29
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

int ri() {
    int n;
    scanf("%d", &n);
    return n;
}
struct Hen {
	int from;
	int to;
	int cost;
	int id;
};
std::vector<std::vector<Hen> > hens;
std::vector<int> ord;
int cnt = 0;
std::vector<std::vector<int> > parent;
std::vector<int> depth;
std::vector<int64_t> cost;
void dfs(int i, int prev) {
	ord[i] = cnt++;
	if (prev != -1) {
		int cur = prev;
		parent[i].push_back(cur);
		for (int k = 0; k < (int) parent[cur].size(); k++) parent[i].push_back(cur = parent[cur][k]);
	}
	for (auto &j : hens[i]) {
		if (j.to != prev) {
			depth[j.to] = depth[i] + 1;
			cost[j.to] = cost[i] + j.cost;
			dfs(j.to, i);
		}
	}
}
int lca(int i, int j) {
	if (i == j) return i;
	if (depth[i] > depth[j]) std::swap(i, j);
	int diff = depth[j] - depth[i];
	for (int k = 20; k >= 0; k--) if (diff >> k & 1) j = parent[j][k];
	if (i == j) return i;
	for (int k = 20; k >= 0; k--) if (k < (int) parent[i].size() && parent[i][k] != parent[j][k])
		i = parent[i][k], j = parent[j][k];
	return parent[i][0];
}
int main() {
	int n = ri();
	hens.resize(n);
	for (int i = 0; i + 1 < n; i++) {
		int a = ri();
		int b = ri();
		int c = ri();
		hens[a].push_back({a, b, c, i});
		hens[b].push_back({b, a, c, i});
	}
	ord.resize(n);
	parent.resize(n);
	depth.resize(n);
	cost.resize(n);
	dfs(0, -1);
	int q = ri();
	for (int i = 0; i < q; i++) {
		int k = ri();
		std::vector<std::pair<int, int> > ords;
		for (int i = 0; i < k; i++) {
			int x = ri();
			ords.push_back({ord[x], x});
		}
		std::sort(ords.begin(), ords.end());
		int64_t res = 0;
		for (int i = 0; i < (int) ords.size(); i++) {
			int r0 = ords[i].second;
			int r1 = ords[(i + 1) % ords.size()].second;
			int l = lca(r0, r1);
			res += cost[r0] + cost[r1] - 2 * cost[l];
		}
		std::cout << res / 2 << std::endl;
	}
	
    return 0;
}
0