-
Notifications
You must be signed in to change notification settings - Fork 86
Expand file tree
/
Copy path035-04.cpp
More file actions
75 lines (75 loc) · 1.69 KB
/
035-04.cpp
File metadata and controls
75 lines (75 loc) · 1.69 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <vector>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
int main() {
cin.tie(0);
ios_base::sync_with_stdio(false);
int N;
cin >> N;
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);
}
int bits = 0;
while ((1 << bits) < N) ++bits;
vector<vector<int> > par(bits, vector<int>(N));
vector<int> depth(N), id(N);
int vert_id = 0;
function<void(int, int)> build_tree = [&](int pos, int pre) {
par[0][pos] = pre;
id[pos] = vert_id++;
for (int i : G[pos]) {
if (i == pre) continue;
depth[i] = depth[pos] + 1;
build_tree(i, pos);
}
};
build_tree(0, 0);
for (int i = 1; i < bits; ++i) {
for (int j = 0; j < N; ++j) {
par[i][j] = par[i - 1][par[i - 1][j]];
}
}
function<int(int, int)> lca = [&](int va, int vb) {
if (depth[va] < depth[vb]) swap(va, vb);
for (int i = bits - 1; i >= 0; --i) {
if (depth[va] - depth[vb] >= (1 << i)) {
va = par[i][va];
}
}
if (va == vb) return va;
for (int i = bits - 1; i >= 0; --i) {
if (par[i][va] != par[i][vb]) {
va = par[i][va];
vb = par[i][vb];
}
}
return par[0][va];
};
int Q;
cin >> Q;
for (int i = 0; i < Q; ++i) {
int verts;
cin >> verts;
vector<int> sel(verts);
for (int j = 0; j < verts; ++j) {
cin >> sel[j];
--sel[j];
}
sort(sel.begin(), sel.end(), [&](int va, int vb) {
return id[va] < id[vb];
});
int answer = 0;
for (int j = 0; j < verts; ++j) {
answer += depth[sel[j]];
answer -= depth[lca(sel[j], sel[(j + 1) % verts])];
}
cout << answer << '\n';
}
return 0;
}