#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
constexpr int LOG = 18;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, timer = 0;
cin >> n;
vector<int> h(n + 1), d(n + 1), l(n + 1);
vector<vector<pair<int, int> > > adj(n + 1);
vector anc(LOG + 1, vector<int>(n + 1));
for (int i = 1; i < n; ++i) {
int u, v, w;
cin >> u >> v >> w;
adj[u + 1].emplace_back(v + 1, w);
adj[v + 1].emplace_back(u + 1, w);
}
auto dfs = [&](auto &&self, int u, int p) -> void {
anc[0][u] = p;
l[u] = ++timer;
for (int i = 1; i <= LOG; ++i)
anc[i][u] = anc[i - 1][anc[i - 1][u]];
for (auto &[v, w]: adj[u]) {
if (v == p) continue;
d[v] = d[u] + 1;
h[v] = h[u] + w;
self(self, v, u);
}
};
dfs(dfs, 1, 0);
auto lca = [&](int a, int b) {
if (d[a] < d[b]) swap(a, b);
for (int i = LOG; i >= 0; --i) {
if (d[a] - (1 << i) >= d[b])
a = anc[i][a];
}
if (a == b) {
return a;
} else {
for (int i = LOG; i >= 0; --i) {
if (anc[i][a] != anc[i][b]) {
a = anc[i][a];
b = anc[i][b];
}
}
return anc[0][a];
}
};
int q;
cin >> q;
auto dist = [&](int a, int b) {
return h[a] + h[b] - 2 * h[lca(a, b)];
};
while (q--) {
vector<int> arr(5);
for (auto &it: arr) {
cin >> it;
it += 1;
}
sort(arr.begin(), arr.end(), [&](int a, int b) {
return l[a] < l[b];
});
int ans = dist(lca(arr[0], arr[4]), arr[0]);
for (int i = 0; i < 4; ++i)
ans += dist(arr[i], arr[i + 1]);
ans += dist(lca(arr[0], arr[4]), arr[4]);
cout << ans / 2 << '\n';
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
336 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
54 ms |
9300 KB |
Output is correct |
2 |
Correct |
55 ms |
10216 KB |
Output is correct |
3 |
Correct |
56 ms |
10120 KB |
Output is correct |
4 |
Correct |
53 ms |
10216 KB |
Output is correct |
5 |
Correct |
54 ms |
10180 KB |
Output is correct |
6 |
Correct |
54 ms |
10120 KB |
Output is correct |
7 |
Correct |
52 ms |
10120 KB |
Output is correct |
8 |
Correct |
56 ms |
10124 KB |
Output is correct |
9 |
Correct |
56 ms |
10120 KB |
Output is correct |
10 |
Correct |
57 ms |
10112 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
29 ms |
8332 KB |
Output is correct |
2 |
Correct |
36 ms |
9732 KB |
Output is correct |
3 |
Correct |
34 ms |
9608 KB |
Output is correct |
4 |
Correct |
37 ms |
9740 KB |
Output is correct |
5 |
Correct |
38 ms |
9608 KB |
Output is correct |
6 |
Correct |
36 ms |
9608 KB |
Output is correct |
7 |
Correct |
37 ms |
9608 KB |
Output is correct |
8 |
Correct |
34 ms |
9608 KB |
Output is correct |
9 |
Correct |
35 ms |
9592 KB |
Output is correct |
10 |
Correct |
42 ms |
9616 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
336 KB |
Output is correct |
2 |
Correct |
54 ms |
9300 KB |
Output is correct |
3 |
Correct |
55 ms |
10216 KB |
Output is correct |
4 |
Correct |
56 ms |
10120 KB |
Output is correct |
5 |
Correct |
53 ms |
10216 KB |
Output is correct |
6 |
Correct |
54 ms |
10180 KB |
Output is correct |
7 |
Correct |
54 ms |
10120 KB |
Output is correct |
8 |
Correct |
52 ms |
10120 KB |
Output is correct |
9 |
Correct |
56 ms |
10124 KB |
Output is correct |
10 |
Correct |
56 ms |
10120 KB |
Output is correct |
11 |
Correct |
57 ms |
10112 KB |
Output is correct |
12 |
Correct |
29 ms |
8332 KB |
Output is correct |
13 |
Correct |
36 ms |
9732 KB |
Output is correct |
14 |
Correct |
34 ms |
9608 KB |
Output is correct |
15 |
Correct |
37 ms |
9740 KB |
Output is correct |
16 |
Correct |
38 ms |
9608 KB |
Output is correct |
17 |
Correct |
36 ms |
9608 KB |
Output is correct |
18 |
Correct |
37 ms |
9608 KB |
Output is correct |
19 |
Correct |
34 ms |
9608 KB |
Output is correct |
20 |
Correct |
35 ms |
9592 KB |
Output is correct |
21 |
Correct |
42 ms |
9616 KB |
Output is correct |
22 |
Correct |
57 ms |
9352 KB |
Output is correct |
23 |
Correct |
41 ms |
8840 KB |
Output is correct |
24 |
Correct |
54 ms |
10036 KB |
Output is correct |
25 |
Correct |
52 ms |
9972 KB |
Output is correct |
26 |
Correct |
54 ms |
10060 KB |
Output is correct |
27 |
Correct |
57 ms |
10056 KB |
Output is correct |
28 |
Correct |
56 ms |
10120 KB |
Output is correct |
29 |
Correct |
56 ms |
10128 KB |
Output is correct |
30 |
Correct |
57 ms |
10032 KB |
Output is correct |
31 |
Correct |
55 ms |
10120 KB |
Output is correct |