/// dc nu mergeeee
#include <bits/stdc++.h>
#include "factories.h"
#define DIM 500010
#define INF 1000000000000000000LL
using namespace std;
vector <pair<int,int> > L[DIM];
long long aint[DIM*4][2],dp[DIM];
int level[DIM],fth[DIM],first[DIM],p[DIM*3],E[DIM*3];
pair <int,int> rmq[22][DIM*3],poz[DIM]; /// bv
vector <int> v;
int n,k,el,q,i;
long long sol0,sol1;
int a[DIM],b[DIM],d[DIM];
void dfs (int nod, int tata){
E[++k] = nod;
level[nod] = 1 + level[tata];
first[nod] = k;
fth[nod] = tata;
poz[nod].first = ++el;
for (auto it : L[nod]){
int vecin = it.first;
if (vecin != tata){
dp[vecin] = dp[nod] + it.second;
dfs (vecin,nod);
E[++k] = nod;
}
}
poz[nod].second = el;
}
void build (int nod, int st, int dr){
aint[nod][0] = aint[nod][1] = INF;
if (st == dr)
return;
int mid = (st+dr)>>1;
build (nod<<1,st,mid);
build ((nod<<1)|1,mid+1,dr);
}
void update (int nod, int st, int dr, int poz, long long val, int tip){
//if (val == INF)
// aint[nod][0] = aint[nod][1] = INF;
if (st == dr){
aint[nod][tip] = val;
return;
}
int mid = (st+dr)>>1;
if (poz <= mid)
update (nod<<1,st,mid,poz,val,tip);
else update ((nod<<1)|1,mid+1,dr,poz,val,tip);
aint[nod][0] = min (aint[nod<<1][0],aint[(nod<<1)|1][0]);
aint[nod][1] = min (aint[nod<<1][1],aint[(nod<<1)|1][1]);
}
void query (int nod, int st, int dr, int x, int y){
if (x <= st && dr <= y){
sol0 = min (sol0,aint[nod][0]);
sol1 = min (sol1,aint[nod][1]);
return;
}
int mid = (st+dr)>>1;
if (x <= mid)
query (nod<<1,st,mid,x,y);
if (y > mid)
query ((nod<<1)|1,mid+1,dr,x,y);
}
int cmp (int a, int b){
return poz[a].first < poz[b].first;
}
int get_lca (int x, int y){
int pozx = first[x], pozy = first[y];
if (pozx > pozy)
swap (pozx,pozy);
int nr = p[pozy-pozx+1];
pair <int,int> sol = min (rmq[nr][pozx],rmq[nr][pozy-(1<<nr)+1]);
return E[sol.second];
}
void Init (int _n, int a[], int b[], int d[]){
n = _n;
for (int i=0;i<n-1;i++){
int x = a[i], y = b[i], cost = d[i];
x++, y++;
L[x].push_back(make_pair(y,cost));
L[y].push_back(make_pair(x,cost));
}
k = 0, el = 0;
dfs (1,0);
build (1,1,n);
for (int i=1;i<=k;i++)
rmq[0][i] = make_pair(level[E[i]],i);
for (int i=1;(1<<i)<=k;i++)
for (int j=1;j<=k;j++){
rmq[i][j] = rmq[i-1][j];
if (j + (1<<(i-1)) <= k && rmq[i-1][j + (1<<(i-1))].first < rmq[i][j].first)
rmq[i][j] = rmq[i-1][j + (1<<(i-1))];
}
for (int i=2;i<=k;i++)
p[i] = p[i/2] + 1;
}
long long Query (int el, int a[], int el2, int b[]){
int i;
v.clear();
for (i=0;i<el;i++){
a[i]++;
v.push_back(a[i]);
update (1,1,n,poz[a[i]].first,dp[a[i]],0);
}
for (i=0;i<el2;i++){
b[i]++;
v.push_back(b[i]);
update (1,1,n,poz[b[i]].first,dp[b[i]],1);
}
sort (v.begin(),v.end(),cmp);
long long sol = INF;
for (i=1;i<v.size();i++){
int lca = get_lca(v[i],v[i-1]);
sol0 = INF, sol1 = INF;
query (1,1,n,poz[lca].first,poz[lca].second);
if (sol0 != INF && sol1 != INF)
sol = min (sol,sol0 + sol1 - 2 * dp[lca]);
}
/// le demarchez la loc
for (i=0;i<el;i++)
update (1,1,n,poz[a[i]].first,INF,0);
for (i=0;i<el2;i++)
update (1,1,n,poz[b[i]].first,INF,1);
return sol;
}
/*
int main (){
ifstream cin ("date.in");
ofstream cout ("date.out");
int n,i;
cin>>n>>q;
for (i=0;i<n-1;i++)
cin>>a[i]>>b[i]>>d[i];
Init (n,a,b,d);
//cout<<get_lca(206363,138910)<<" ";
for (;q--;){
int el,el2;
cin>>el>>el2;
for (i=0;i<el;i++)
cin>>a[i];
for (i=0;i<el2;i++)
cin>>b[i];
//if (q == 99999)
cout<<Query(el,a,el2,b)<<"\n";
}
return 0;
}
*/
