/**
* author: Haunted_Cpp
**/
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")
template<typename T> ostream &operator << (ostream &os, const vector<T> &v) { os << '{'; string sep; for (const auto &x : v) os << sep << x, sep = ", "; return os << '}'; }
template<typename T, size_t size> ostream &operator << (ostream &os, const array<T, size> &arr) { os << '{'; string sep; for (const auto &x : arr) os << sep << x, sep = ", "; return os << '}'; }
template<typename A, typename B> ostream &operator << (ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
void debug_out() { cerr << endl; }
template<typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << ' ' << H; debug_out(T...); }
#ifdef LOCAL
#define debug(...) cerr << "(" << #__VA_ARGS__ << "):", debug_out(__VA_ARGS__)
#else
#define debug(...) 47
#endif
const int MAX_N = 5e4 + 5;
const int MAX_K = 20 + 5;
int Time = 0;
vector<int> depth(MAX_N), dist(MAX_N), in(MAX_N), out(MAX_N);
vector<vector<int>> dp(MAX_N, vector<int>(MAX_K, -1));
vector<vector<pair<int, int>>> g(MAX_N);
void dfs(int node = 0, int p = -1) {
in[node] = ++Time;
dp[node][0] = p;
for (auto to : g[node]) {
if (to.first != p) {
depth[to.first] = depth[node] + 1;
dist[to.first] = dist[node] + to.second;
dfs(to.first, node);
}
}
out[node] = Time;
}
int kth(int node, int diff) {
assert(diff >= 0);
for (int i = MAX_K - 1; ~i; i--) {
if ((diff >> i) & 1) {
node = dp[node][i];
}
}
return node;
}
int lca(int u, int v) {
if (depth[u] < depth[v]) swap(u, v);
u = kth(u, depth[u] - depth[v]);
if (u == v) return u;
for (int i = MAX_K - 1; ~i; i--) {
if (dp[u][i] != dp[v][i]) {
u = dp[u][i];
v = dp[v][i];
}
}
return dp[u][0];
}
int get_dist(int u, int v) {
return dist[u] + dist[v] - 2 * dist[lca(u, v)];
}
bool in_subtree(int u, int v) {
return (in[u] <= in[v] && out[u] >= out[v]);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
for (int i = 0; i < n - 1; i++) {
int st, et, w;
cin >> st >> et >> w;
g[st].emplace_back(et, w);
g[et].emplace_back(st, w);
}
dfs();
for (int j = 1; j < MAX_K; j++) {
for (int i = 0; i < n; i++) {
if (~dp[i][j - 1]) {
dp[i][j] = dp[dp[i][j - 1]][j - 1];
}
}
}
int q;
cin >> q;
const int T = 5;
vector<int> arr(T);
while(q--) {
for (int i = 0; i < T; i++) cin >> arr[i];
pair<int, int> best_way = {1e9, 1e9};
vector<pair<int, int>> check;
for (int i = 0; i < T; i++) {
for(int j = 0; j < T; j++) {
const int LCA = lca(arr[i], arr[j]);
check.emplace_back(depth[LCA], LCA);
best_way = min(best_way, {depth[LCA], LCA});
}
}
sort(check.begin(), check.end());
set<int> vis;
function<int(int)> solve = [&](int source) {
vis.insert(source);
const int d = depth[source];
int s = 0;
for (auto to : check) {
const int TO = to.second;
if(vis.find(TO) != vis.end()) continue;
if (d <= depth[TO] && in_subtree(source, TO)) {
vis.insert(TO);
s += get_dist(source, TO) + solve(TO);
}
}
return s;
};
cout << solve(best_way.first) << '\n';
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
8960 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
209 ms |
12664 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
45 ms |
10872 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
8960 KB |
Output is correct |
| 2 |
Incorrect |
209 ms |
12664 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
