#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
int const NN = 500005;
int const LOG = log2(NN)+1;
vector<pair<int, long long>> g[NN];
long long dist[NN];
int tin[NN], tout[NN];
int par[NN][LOG];
int tt=0;
void f1(int u, int p =0, long long d = 0)
{
dist[u] = d;
tt++;
tin[u]=tt;
par[u][0]=p;
for(int i = 1; i < LOG; i++)
{
par[u][i] = par[par[u][i-1]][i-1];
}
for(auto i: g[u])
{
if(i.first==p)continue;
f1(i.first, u, d+i.second);
}
tout[u]=tt;
}
bool isanc (int u, int v)
{
return (tin[u] <= tin[v] && tout[v] <= tout[u]);
}
int lca(int u, int v)
{
if(isanc(u,v)) return u;
if(isanc(v, u)) return v;
for(int i = LOG - 1; i >= 0; i--)
{
if(!isanc(par[u][i], v)) u = par[u][i];
}
return par[u][0];
}
void Init(int N, int A[], int B[], int D[]) {
for(int i =0; i < N-1; i++)
{
g[A[i]].push_back({B[i], D[i]});
g[B[i]].push_back({A[i], D[i]});
}
f1(0);
}
long long Query(int S, int X[], int T, int Y[]) {
long long rez=1e18;
for(int i =0; i < S; i++)
{
for(int j = 0; j < T; j++)
{
rez=min(rez, dist[X[i]]+dist[Y[j]] - dist[lca(X[i],Y[j])]*2);
}
}
return rez;
}
