#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, ll> pii;
#define pb push_back
#define all(x) x.begin(), x.end()
// #define int ll
// #define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const ll inf = 1e18 + 10;
const int maxn = 1e6 + 10;
ll dist[maxn], sub[maxn];
vector<pii> G[maxn], cent[maxn];
bool dead[maxn];
int dfs_sz(int v, int p) {
sub[v] = 1;
for (auto [u, w] : G[v]) {
if (u == p || dead[u]) continue;
sub[v] += dfs_sz(u, v);
}
return sub[v];
}
int centroid(int v, int p, int sz) {
for (auto [u, w] : G[v]) {
if (u == p || dead[u]) continue;
if (sz < sub[u] * 2)
return centroid(u, v, sz);
}
return v;
}
void add(int v, int p, int tag, int d = 0) {
cent[v].pb({tag, d});
for (auto [u, w] : G[v]) {
if (u == p || dead[u]) continue;
add(u, v, tag, d + w);
}
}
void decomp(int v) {
int cen = centroid(v, 0, dfs_sz(v, 0));
add(cen, 0, cen);
for (auto [u, w] : G[v]) {
if (dead[u]) continue;
decomp(u);
}
}
void Init(int N, int A[], int B[], int D[]) {
for (int i = 0; i < N - 1; i++) {
G[A[i]].pb({B[i], D[i]});
G[B[i]].pb({A[i], D[i]});
}
}
ll Query(int S, int X[], int T, int Y[]) {
for (int i = 0; i < S; i++) {
for (auto [u, d] : cent[X[i]]) {
dist[u] = inf;
}
}
for (int i = 0; i < T; i++) {
for (auto [u, d] : cent[Y[i]]) {
dist[u] = min(dist[u], d);
}
}
ll ans = inf;
for (int i = 0; i < S; i++) {
for (auto [u, d] : cent[X[i]]) {
ans = min(ans, d + dist[u]);
}
}
return ans;
}
