#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e18;
int n;
vector<vector<pair<int, ll>>> t;
vector<vector<pair<int, ll>>> dist;
vector<ll> min_dist;
int decompose(int s, int depth, vector<int> &subt_n, vector<bool> &done) {
auto dfs1 = [s, &done, &subt_n](const auto &self, int u, int par) -> void {
subt_n[u] = 1;
for (auto [v, d] : t[u]) {
if (done[v] or v == par) continue;
self(self, v, u);
subt_n[u] += subt_n[v];
}
};
dfs1(dfs1, s, -1);
int cn = subt_n[s];
auto dfs2 = [cn, &done, &subt_n](const auto &self, int u, int par) -> int {
for (auto [v, d] : t[u]) {
if (done[v] or v == par) continue;
if (subt_n[v] * 2 > cn) return self(self, v, u);
}
return u;
};
int c = dfs2(dfs2, s, -1);
done[c] = 1;
dist[c][depth] = make_pair(c, 0);
auto dfs3 = [c, depth, &done](const auto &self, int u, int par) -> void {
for (auto [v, d] : t[u]) {
if (done[v] or v == par) continue;
dist[v][depth] = make_pair(c, dist[u][depth].second + d);
self(self, v, u);
}
};
dfs3(dfs3, c, -1);
for (auto [v, d] : t[c]) {
if (done[v]) continue;
decompose(v, depth + 1, subt_n, done);
}
return c;
}
void Init(int N, int A[], int B[], int D[]) {
n = N;
t.resize(n);
for (int i = 0; i < n - 1; i++) {
t[A[i]].push_back(make_pair(B[i], D[i]));
t[B[i]].push_back(make_pair(A[i], D[i]));
}
dist.resize(n, vector<pair<int, ll>>(19, make_pair(-1, INF)));
vector<int> subt_n(n, 0);
vector<bool> done(n, 0);
decompose(0, 0, subt_n, done);
min_dist.resize(n, INF);
}
ll Query(int S, int X[], int T, int Y[]) {
for (int i = 0; i < T; i++) {
for (auto [v, d] : dist[Y[i]]) {
if (v == -1) break;
min_dist[v] = min(min_dist[v], d);
}
}
ll ret = INF;
for (int i = 0; i < S; i++) {
for (auto [v, d] : dist[X[i]]) {
if (v == -1) break;
ret = min(ret, d + min_dist[v]);
}
}
for (int i = 0; i < T; i++) {
for (auto [v, d] : dist[Y[i]]) {
if (v == -1) break;
min_dist[v] = INF;
}
}
return ret;
}
