#include<bits/stdc++.h>
#include "factories.h"
#define ll long long
#define uset unordered_set
using namespace std;
const int LOG=19;
const ll INF=1e18;
int n;
vector<vector<pair<int,ll>>>adj,adjv;
vector<ll>dis1;
vector<int>tin,tout;
vector<vector<int>>par;
int dfs(int u=0,int p=-1,int t=0){
tin[u]=t++;
for(auto[v,d]:adj[u]){
if(v==p)continue;
par[0][v]=u;
dis1[v]=dis1[u]+d;
t=dfs(v,u,t);
}
tout[u]=t++;
return t;
}
int 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[i][u],v))u=par[i][u];
}
return par[0][u];
}
ll dis(int u,int v){
return dis1[u]+dis1[v]-2*dis1[lca(u,v)];
}
void Init(int N, int A[], int B[], int D[]) {
n=N;
adj.assign(n,{});
adjv.assign(n,{});
dis1.assign(n,0);
tin.assign(n,0);
tout.assign(n,0);
par.assign(LOG,vector<int>(n));
par[0][0]=0;
for(int i=0;i<n-1;i++){
int u=A[i];
int v=B[i];
int d=D[i];
adj[u].push_back({v,d});
adj[v].push_back({u,d});
}
dfs();
for(int i=1;i<LOG;i++){
for(int u=0;u<n;u++){
int v=par[i-1][u];
par[i][u]=par[i-1][v];
}
}
}
uset<int>s;
int buildvt(vector<int>&nodes){
sort(nodes.begin(),nodes.end(),[&](int&u,int&v){return tin[u]<tin[v];});
s.clear();
for(int u:nodes)s.insert(u);
for(int i=nodes.size()-2;i;i--){
int u=nodes[i];
int v=nodes[i+1];
int w=lca(u,v);
if(!s.count(w)){
s.insert(w);
nodes.push_back(w);
}
}
sort(nodes.begin(),nodes.end(),[&](int&u,int&v){return tin[u]<tin[v];});
vector<tuple<int,int,ll>>edg;
vector<int>ord;
ord.push_back(nodes[0]);
for(int i=1;i<nodes.size();i++){
if(nodes[i]==nodes[i-1])continue;
int u=nodes[i];
while(!isanc(ord.back(),u))ord.pop_back();
int v=ord.back();
ord.push_back(u);
ll d=dis(u,v);
adjv[u].push_back({v,d});
adjv[v].push_back({u,d});
}
return nodes[0];
}
ll ans;
bitset<500005>sx,sy;
array<ll,2>dfsvt(int u,int p=-1){
array<ll,2>res={INF,INF};
for(auto[v,d]:adjv[u]){
if(v==p)continue;
auto res1=dfsvt(v,u);
if(res1[0]<INF){
res[0]=min(res[0],res1[0]+d);
}
if(res1[1]<INF){
res[1]=min(res[1],res1[1]+d);
}
}
if(sx[u]){
res[0]=0;
ans=min(ans,res[1]);
}
if(sy[u]){
res[1]=0;
ans=min(ans,res[0]);
}
if(res[0]<INF&&res[1]<INF){
ans=min(ans,res[0]+res[1]);
}
return res;
}
ll Query(int S, int X[], int T, int Y[]) {
vector<int>nodes;
ans=INF;
for(int i=0;i<S;i++){
int u=X[i];
nodes.push_back(u);
sx[u]=1;
sy[u]=0;
}
for(int i=0;i<T;i++){
int u=Y[i];
nodes.push_back(u);
sx[u]=0;
sy[u]=1;
}
int r=buildvt(nodes);
dfsvt(r);
for(int u:nodes){
adjv[u].clear();
sx[u]=sy[u]=0;
}
return ans;
}
