#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int inf = 1e9 + 7;
const ll infll = 1e18;
struct Edge {
int to, w;
};
vector<vector<Edge>> g;
vector<bool> used;
vector<int> sz, par;
vector<vector<ll>> dist;
vector<ll> closest;
void dfs_sz(int v, int p = -1) {
sz[v] = 1;
for (auto [u, w] : g[v]) {
if (u != p && !used[u]) {
dfs_sz(u, v);
sz[v] += sz[u];
}
}
}
void dfs_dist(int v, int p = -1, ll d = 0) {
dist[v].push_back(d);
for (auto [u, w] : g[v]) {
if (u != p && !used[u]) {
dfs_dist(u, v, d + w);
}
}
}
int centroid(int v, int p, int n) {
for (auto [u, w] : g[v]) {
if (u != p && !used[u]) {
if (sz[u] * 2 > n) {
return centroid(u, v, n);
}
}
}
return v;
}
void build(int v, int p = -1) {
dfs_sz(v);
dfs_dist(v);
par[v] = p;
used[v] = 1;
for (auto [u, w] : g[v]) {
if (!used[u]) {
build(centroid(u, v, sz[u]), v);
}
}
}
void Init(int N, int A[], int B[], int D[]) {
g.resize(N);
for (int i = 0; i < N - 1; ++i) {
int u = A[i], v = B[i], w = D[i];
g[u].push_back({v, w});
g[v].push_back({u, w});
}
used.resize(N);
sz.resize(N);
par.resize(N);
dist.resize(N);
dfs_sz(0);
build(centroid(0, -1, sz[0]));
closest.resize(N, infll);
}
long long Query(int S, int X[], int T, int Y[]) {
for (int i = 0; i < S; ++i) {
int v = X[i];
int u = v;
int j = (int) dist[v].size() - 1;
while (u != -1) {
closest[u] = min(closest[u], dist[v][j]);
u = par[u];
--j;
}
}
ll ans = infll;
for (int i = 0; i < T; ++i) {
int v = Y[i];
int u = v;
int j = (int) dist[v].size() - 1;
while (u != -1) {
ans = min(ans, closest[u] + dist[v][j]);
u = par[u];
--j;
}
}
for (int i = 0; i < S; ++i) {
int v = X[i];
int u = v;
int j = (int) dist[v].size() - 1;
while (u != -1) {
closest[u] = infll;
u = par[u];
--j;
}
}
return ans;
}
