#include <bits/stdc++.h>
#include "factories.h"
#define pb push_back
#define s second
#define f first
#define ll long long
using namespace std;
const int M = 5e5 + 5;
const ll inf = 1e18 + 5;
int parent[M],dep[M];
bool fix[M];
ll dp[M],dis[25][M];
vector <pair <int,ll> > v[M],path;
int findcentroid(int x,int par,int n,int ¢roid,int h){
int s = 1;
for (auto [to,w]: v[x])
if (!fix[to] && to != par) s += findcentroid(to,x,n,centroid,h);
if (centroid==-1 && (2*s >= n || par == -1)) centroid = x;
return s;
}
void dfs(int x,int par,int h){
for (auto [to,w]: v[x]){
if (!fix[to] && to != par){
dis[h][to] = dis[h][x] + w;
dfs(to,x,h);
}
}
}
void build(int x,int par,int n,int h){
int centroid = -1; ll edge_weight = 0;
findcentroid(x,-1,n,centroid,h);
fix[centroid] = 1;
parent[centroid] = par;
dep[centroid] = h;
dfs(centroid,-1,h);
for (auto [to,w]: v[centroid])
if (!fix[to]) build(to,centroid,n/2,h + 1);
}
void Init(int n, int A[], int B[], int D[]) {
for (int i=0;i<n-1;i++){
v[A[i] + 1].pb({B[i] + 1,D[i]});
v[B[i] + 1].pb({A[i] + 1,D[i]});
}
for (int i = 1; i <= n; i++) dp[i] = inf;
build(1,-1,n,1);
}
long long Query(int S, int X[], int T, int Y[]) {
ll ans = inf;
vector <int> v; v.clear();
for (int i=0;i<S;i++){
X[i]++;
int x = X[i];
while (x != -1){
dp[x] = min(dp[x], dis[dep[x]][X[i]]);
v.pb(x);
x = parent[x];
}
}
for (int i=0;i<T;i++){
Y[i]++;
int y = Y[i];
while (y != -1){
ans = min(ans,dis[dep[y]][Y[i]] + dp[y]);
y = parent[y];
}
}
for (int x: v) dp[x] = inf;
return ans;
}
