#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
const long long LINF = (long long) 1e18;
int n, max_log;
vector< vector< pair<int, int> > > g;
vector<int> sz, cd;
vector<bool> used;
int calc_sizes(int u, int par) {
sz[u] = 1;
for (auto &[v, w] : g[u]) if (v != par && !used[v]) sz[u] += calc_sizes(v, u);
return sz[u];
}
int find_centroid(int u, int par, int cur_sz) {
for (auto &[v, w] : g[u]) if (v != par && !used[v] && sz[v] > cur_sz / 2) return find_centroid(v, u, cur_sz);
return u;
}
void decompose(int u, int par) {
int centroid = find_centroid(u, par, calc_sizes(u, par));
cd[centroid] = par; used[centroid] = true;
for (auto &[v, w] : g[centroid]) if (!used[v] && v != par) decompose(v, centroid);
}
int dfs_cnt = 0;
vector< vector<int> > up;
vector<int> dfs_in, dfs_out;
vector<long long> depth;
void dfs(int u, int par) {
dfs_in[u] = dfs_cnt++;
up[u][0] = par;
for (int i = 1; i <= max_log; i++) up[u][i] = up[up[u][i - 1]][i - 1];
for (auto &[v, w] : g[u]) {
if (v == par) continue;
depth[v] = depth[u] + w;
dfs(v, u);
}
dfs_out[u] = dfs_cnt++;
}
bool is_anc(int u, int v) {
return dfs_in[u] <= dfs_in[v] && dfs_out[v] <= dfs_out[u];
}
int lca(int u, int v) {
if (is_anc(u, v)) return u;
if (is_anc(v, u)) return v;
for (int i = max_log; i >= 0; i--) if (!is_anc(up[u][i], v)) u = up[u][i];
return up[u][0];
}
long long dist(int u, int v) {
return depth[u] + depth[v] - 2 * depth[lca(u, v)];
}
vector<long long> closest;
void Init(int N, int A[], int B[], int D[]) {
n = N;
max_log = ceil(log2(n + 1));
g.resize(n);
for (int i = 0; i < n - 1; i++) {
g[A[i]].emplace_back(B[i], D[i]);
g[B[i]].emplace_back(A[i], D[i]);
}
cd.resize(n);
sz.resize(n); used.assign(n, false);
decompose(0, -1);
depth.resize(n); depth[0] = 0;
dfs_in.resize(n); dfs_out.resize(n);
up.assign(n, vector<int>(max_log + 1));
dfs(0, 0);
closest.assign(n, LINF);
}
long long Query(int S, int X[], int T, int Y[]) {
stack<int> st;
for (int i = 0; i < S; i++) {
for (int u = X[i]; u != -1; u = cd[u]) {
closest[u] = min(closest[u], dist(X[i], u));
st.push(u);
}
}
long long ans = LINF;
for (int i = 0; i < T; i++) {
for (int u = Y[i]; u != -1; u = cd[u]) {
ans = min(ans, closest[u] + dist(Y[i], u));
}
}
while (!st.empty()) {
closest[st.top()] = LINF;
st.pop();
}
return ans;
}
