#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int K = 20;
const ll INF = 1e16;
vector<vector<pair<int, ll>>> g;
vector<int> tin, tout, par;
vector<ll> depth, closest;
vector<vector<int>> up;
int timer, n;
void dfs(int u, int p = -1, ll d = 0) {
tin[u] = timer++;
depth[u] = d;
for (auto [v, w] : g[u]) {
if (v == p) continue;
up[v][0] = u;
dfs(v, u, d + w);
}
tout[u] = timer++;
}
bool is_ancestor(int u, int v) {
return tin[u] <= tin[v] && tout[v] <= tout[u];
}
void preprocess_lca() {
for (int k = 1; k < K; k++) {
for (int i = 1; i <= n; i++) {
up[i][k] = up[up[i][k-1]][k-1];
}
}
}
int lca(int u, int v) {
if (is_ancestor(u, v)) return u;
if (is_ancestor(v, u)) return v;
for (int i = K-1; i >= 0; i--) {
if (up[u][i] && !is_ancestor(up[u][i], v)) u = up[u][i];
}
return up[u][0];
}
ll calc_dist(int u, int v) {
int x = lca(u, v);
return depth[u] + depth[v] - 2 * depth[x];
}
void build_centroid_tree() {
par = vector<int>(n+1);
vector<int> siz(n+1);
vector<bool> vis(n+1);
auto calc_siz = [&](auto &&self, int u, int p = -1) -> void {
siz[u] = 1;
for (auto [v, w] : g[u]) {
if (v == p || vis[v]) continue;
self(self, v, u);
siz[u] += siz[v];
}
};
auto find_centroid = [&](auto &&self, int u, int th, int p = -1) -> int {
for (auto [v, w] : g[u]) {
if (v == p || vis[v]) continue;
if (siz[v] > th) return self(self, v, th, u);
}
return u;
};
auto decomp = [&](auto &&self, int u) -> int {
calc_siz(calc_siz, u);
u = find_centroid(find_centroid, u, siz[u]/2);
vis[u] = 1;
for (auto [v, w] : g[u]) {
if (!vis[v]) {
int x = self(self, v);
par[x] = u;
}
}
return u;
};
decomp(decomp, 1);
}
void Init(int N, int A[], int B[], int D[]) {
n = N;
g = vector<vector<pair<int, ll>>>(n+1);
tin = vector<int>(n+1);
tout = vector<int>(n+1);
depth = vector<ll>(n+1);
closest = vector<ll>(n+1, INF);
up = vector<vector<int>>(n+1, vector<int>(K));
timer = 1;
for (int i = 0; i < n-1; i++) {
g[A[i]+1].emplace_back(B[i]+1, D[i]);
g[B[i]+1].emplace_back(A[i]+1, D[i]);
}
dfs(1);
preprocess_lca();
build_centroid_tree();
}
long long Query(int S, int X[], int T, int Y[]) {
// ll ans = INF;
// for (int i = 0; i < S; i++) {
// for (int j = 0; j < T; j++) {
// cerr << X[i]+1 << " " << Y[j]+1 << ": " << calc_dist(X[i]+1, Y[j]+1) << endl;
// ans = min(ans, calc_dist(X[i]+1, Y[j]+1));
// }
// }
for (int i = 0; i < S; i++) {
int u = X[i]+1;
int v = u;
while (v) {
closest[v] = min(closest[v], calc_dist(v, u));
v = par[v];
}
}
ll ans = INF;
for (int i = 0; i < T; i++) {
int u = Y[i]+1;
int v = u;
while (v) {
ans = min(ans, closest[v] + calc_dist(u, v));
v = par[v];
}
}
for (int i = 0; i < S; i++) {
int u = X[i]+1;
int v = u;
while (v) {
closest[v] = INF;
v = par[v];
}
}
return ans;
}
