#include "factories.h"
#define M 1<<19
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll TRE[2][2*M],dep[M],dd[M];
ll q(ll*T,int i,int l,int r,int tl,int tr){
if(l>tr||tl>r) return 1e18;
if(tl<=l&&r<=tr) return T[i];
return min(q(T,i*2,l,l+r>>1,tl,tr),
q(T,i*2+1,l+r+2>>1,r,tl,tr));
}
void upd(ll*T,int i,int l,int r,int p,ll x){
if(l==r)return void(T[i]=x);
if(l+r>>1<p)
upd(T,i*2+1,l+r+2>>1,r,p,x);
else upd(T,i*2,l,l+r>>1,p,x);
T[i]=min(T[i*2],T[i*2+1]);
}
int pos[M],in[M],out[M],bj[M][20],CC,n;
vector<pair<int,ll>>adj[M];
void dfs(int n){
for(int i=1;i<20;i++)
bj[n][i]=bj[bj[n][i-1]][i-1];
in[n]=++CC,dd[n]=dd[bj[n][0]]+1;
for(auto[i,w]:adj[n]) if(i-bj[n][0])
dep[i]=dep[n]+w,bj[i][0]=n,dfs(i);
out[n]=CC;
}
void Init(int N, int A[], int B[], int D[]) {
for(int i=1;i<2*M;i++)
TRE[1][i]=TRE[0][i]=1e18;
for(int i=0;i<N-1;i++)
adj[A[i]].push_back({B[i],D[i]}),
adj[B[i]].push_back({A[i],D[i]});
n=N,dfs(0);
}
int lca(int a,int b){
if(dd[a]>dd[b])swap(a,b);
for(int i=20;i--;)
if(dd[bj[b][i]]>=dd[a])
b=bj[b][i];
if(a==b)return a;
for(int i=20;i--;)
if(bj[b][i]-bj[a][i])
a=bj[a][i],b=bj[b][i];
return bj[a][0];
}
long long Query(int S, int X[], int T, int Y[]) {
ll ans=1e18;
vector<int>v;
for(int i=0;i<S;i++) v.push_back(X[i]),
upd(*TRE,1,1,n,in[X[i]],dep[X[i]]);
for(int i=0;i<T;i++) v.push_back(Y[i]),
upd(TRE[1],1,1,n,in[Y[i]],dep[Y[i]]);
sort(v.begin(),v.end(),[](int a,int b){return in[a]<in[b];});
for(int i=1;i<S+T;i++){
int x=lca(v[i],v[i-1]);
ans=min(ans,q(*TRE,1,1,n,in[x],out[x])
+q(TRE[1],1,1,n,in[x],out[x])-2*dep[x]);
}
for(auto i:v)upd(*TRE,1,1,n,in[i],1e18);
for(auto i:v)upd(TRE[1],1,1,n,in[i],1e18);
return ans;
}
