#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 rez=1e18;
//int isx[NN], isy[NN];
//long long dp1[NN], dp2[NN];
/*void att(int u, int p =0)
{
if(isx[u])
{
dp1[u] = 0;
}
else dp1[u]=1e18;
if(isy[u])
{
dp2[u] = 0;
}
else dp2[u] = 1e18;
for(auto i: g[u])
{
if(i.first==p)continue;
att(i.first, u);
dp1[u]=min(dp1[u], dp1[i.first]+i.second);
dp2[u]=min(dp2[u], dp2[i.first]+i.second);
}
rez=min(rez, dp1[u]+dp2[u]);
}*/
long long Query(int S, int X[], int T, int Y[]) {
rez=1e18;
if(S <= 10 && T<= 10){
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;
}
else{
/* for(int i =0; i < NN; i++)
{
isx[i]=0;
isy[i]=0;
dp1[i]=1e18;
dp2[i]=1e18;
}
for(int i =0; i < S; i++) isx[X[i]]=1;
for(int j =0; j < T; j++) isy[Y[j]]=1;
att(0);
return rez;*/}
}
