#include<bits/stdc++.h>
#include "factories.h"
using namespace std;
#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()
const int N=5e5+5;
vector<ll>dist(N);
vector<int>sz(N),heavy(N,-1),head(N),par(N);
vector<pair<int,int>>adj[N];
void dfs(int x){
sz[x]=1;
int mx=0;
for(auto [y,w]:adj[x]){
if(y!=par[x]){
dist[y]=dist[x]+w;
par[y]=x;
dfs(y);
sz[x]+=sz[y];
if(sz[y]>mx){
mx=sz[y];
heavy[x]=y;
}
}
}
}
void HLD(int x,int h){
head[x]=h;
if(heavy[x]>-1){
HLD(heavy[x],h);
}
for(auto [y,w]:adj[x]){
if(y!=par[x]&&y!=heavy[x]){
HLD(y,y);
}
}
}
void Init(int n,int a[],int b[],int d[]){
for(int i=0;i<n-1;i++){
adj[a[i]].pb({b[i],d[i]});
adj[b[i]].pb({a[i],d[i]});
}
par[0]=-1;
dfs(0);
HLD(0,0);
}
ll Query(int s,int x[],int t,int y[]){
vector<array<ll,4>>v;
for(int i=0;i<s;i++){
int j=x[i];
v.pb({head[j],-dist[j],x[i],0});
j=head[j];
while(j>0){
j=par[j];
v.pb({head[j],-dist[j],x[i],0});
j=head[j];
}
}
for(int i=0;i<t;i++){
int j=y[i];
v.pb({head[j],-dist[j],y[i],1});
j=head[j];
while(j>0){
j=par[j];
v.pb({head[j],-dist[j],y[i],1});
j=head[j];
}
}
sort(all(v));
vector<array<ll,3>>cur;
ll ans=1e18;
for(int i=0;i<v.size();i++){
cur.pb({-v[i][1],v[i][2],v[i][3]});
if(i==(int)v.size()-1||v[i][0]!=v[i+1][0]){
ll mn0=1e18,mn1=1e18;
for(int j=0;j<cur.size();j++){
if(cur[j][2]==0){
mn0=min(mn0,dist[cur[j][1]]);
ans=min(ans,dist[cur[j][1]]+mn1-2*cur[j][0]);
}
else{
mn1=min(mn1,dist[cur[j][1]]);
ans=min(ans,dist[cur[j][1]]+mn0-2*cur[j][0]);
}
}
cur.clear();
}
}
return ans;
}
