#include<bits/stdc++.h>
using namespace std;
#include "factories.h"
const int MAXN=500005;
int st[MAXN],en[MAXN],p[MAXN][20],id;
long long dis[MAXN],ans,INF=1e18;
vector<vector<pair<int,long long>>>adj,adj2;
void dfs(int v,int par=0,long long dist=0){
st[v]=++id;
p[v][0]=par;
dis[v]=dist;
for(int i=1;i<20;i++)p[v][i]=p[p[v][i-1]][i-1];
for(auto&[u,w]:adj[v]){
if(u==par)continue;
dfs(u,v,dist+w);
}
en[v]=id;
}
pair<long long,long long>solve(int v,int par,map<int,int>&mp){
pair<long long,long long>cur=make_pair(INF, INF);
if(mp[v]==1)cur.first=0;
if(mp[v]==2)cur.second=0;
for(auto[u,w]:adj2[v]){
if(u==par)continue;
auto f=solve(u,v,mp);
f.first+=w;
f.second+=w;
ans=min(ans,cur.first+f.second);
ans=min(ans,cur.second+f.first);
cur.first=min(cur.first,f.first);
cur.second=min(cur.second,f.second);
}
return cur;
}
bool is_ancestor(int u,int v){
return st[u]<=st[v]&&en[u]>=en[v];
}
int LCA(int u,int v){
if(is_ancestor(u,v))return u;
if(is_ancestor(v,u))return v;
for(int i=19;i>=0;i--){
if(is_ancestor(p[u][i],v))continue;
u=p[u][i];
}
return p[u][0];
}
long long cost(int u,int v){
return dis[u]+dis[v]-2*dis[LCA(u,v)];
}
void Init(int N, int A[], int B[], int D[]) {
id=-1;
adj.resize(N);
adj2.resize(N);
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]});
}
dfs(0);
}
long long Query(int S, int X[], int T, int Y[]) {
map<int,int>mp;
vector<int>v;
for(int i=0;i<S;i++){
mp[X[i]]=1;
v.push_back(X[i]);
}
for(int i=0;i<T;i++){
mp[Y[i]]=2;
v.push_back(Y[i]);
}
sort(v.begin(),v.end(),[&](int i,int j){
return st[i]<st[j];
});
int temp_sz=v.size();
for(int i=0;i<temp_sz;i++){
v.push_back(LCA(v[i],v[(i+1)%temp_sz]));
}
sort(v.begin(),v.end());
v.resize(unique(v.begin(),v.end())-v.begin());
sort(v.begin(),v.end(),[&](int i,int j){
return st[i]<st[j];
});
for(int i=0;i<v.size();i++)adj2[v[i]].clear();
vector<int>Stack;
for(int i=0;i<v.size();i++){
while(!Stack.empty()&&!is_ancestor(Stack.back(),v[i]))Stack.pop_back();
if(!Stack.empty()){
long long U=Stack.back(),V=v[i],C=cost(U,V);
adj2[U].push_back({V,C});
adj2[V].push_back({U,C});
}
Stack.push_back(v[i]);
}
ans=LLONG_MAX;
solve(v[0],-1,mp);
return ans;
}
