結果

問題 No.901 K-ary εxtrεεmε
ユーザー QCFiumQCFium
提出日時 2019-11-24 12:51:31
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 256 ms / 3,000 ms
コード長 1,809 bytes
コンパイル時間 1,793 ms
コンパイル使用メモリ 183,652 KB
実行使用メモリ 28,552 KB
最終ジャッジ日時 2024-04-20 08:54:50
合計ジャッジ時間 8,242 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 97 ms
28,552 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 3 ms
5,376 KB
testcase_04 AC 3 ms
5,376 KB
testcase_05 AC 3 ms
5,376 KB
testcase_06 AC 3 ms
5,376 KB
testcase_07 AC 146 ms
19,328 KB
testcase_08 AC 130 ms
19,200 KB
testcase_09 AC 128 ms
18,788 KB
testcase_10 AC 134 ms
19,200 KB
testcase_11 AC 132 ms
19,200 KB
testcase_12 AC 114 ms
19,344 KB
testcase_13 AC 112 ms
19,328 KB
testcase_14 AC 116 ms
19,220 KB
testcase_15 AC 114 ms
19,120 KB
testcase_16 AC 124 ms
19,200 KB
testcase_17 AC 193 ms
19,516 KB
testcase_18 AC 189 ms
19,200 KB
testcase_19 AC 190 ms
19,328 KB
testcase_20 AC 187 ms
19,284 KB
testcase_21 AC 188 ms
19,200 KB
testcase_22 AC 118 ms
19,584 KB
testcase_23 AC 112 ms
19,328 KB
testcase_24 AC 111 ms
19,452 KB
testcase_25 AC 110 ms
18,944 KB
testcase_26 AC 112 ms
19,440 KB
testcase_27 AC 228 ms
19,328 KB
testcase_28 AC 256 ms
19,200 KB
testcase_29 AC 243 ms
19,328 KB
権限があれば一括ダウンロードができます

ソースコード

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