#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
int const NN = 50005;
int const LOG = log2(NN)+1;
vector<pair<int, long long>> g[NN];
long long dist[NN];
int tin[NN], tout[NN];
int par[NN][LOG];
int tt=0;
void f1(int u, int p =0, long long d = 0)
{
dist[u] = d;
tt++;
tin[u]=tt;
par[u][0]=p;
for(int i = 1; i < LOG; i++)
{
par[u][i] = par[par[u][i-1]][i-1];
}
for(auto i: g[u])
{
if(i.first==p)continue;
f1(i.first, u, d+i.second);
}
tout[u]=tt;
}
bool 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[u][i], v)) u = par[u][i];
}
return par[u][0];
}
void Init(int N, int A[], int B[], int D[]) {
for(int i =0; i < N-1; i++)
{
g[A[i]].push_back({B[i], D[i]});
g[B[i]].push_back({A[i], D[i]});
}
f1(0);
}
long long rez=1e18;
int isx[NN], isy[NN];
long long dp1[NN], dp2[NN];
vector<int> nodes;
vector<pair<int, long long>> g2[NN];
void con(int u, int v)
{
if(u==v)return;
g2[u].push_back({v, abs(dist[u]-dist[v])});
g2[v].push_back({u, abs(dist[u]-dist[v])});
}
int create()
{
sort(nodes.begin(), nodes.end(), [](int &i, int &j)
{
return tin[i] < tin[j];
});
for(int i = nodes.size()-2; i >= 0; i--)
{
nodes.push_back(lca(nodes[i], nodes[i+1]));
}
sort(nodes.begin(), nodes.end(), [](int &i, int &j)
{
return tin[i] < tin[j];
});
vector<int> ve;
ve.push_back(nodes[0]);
for(int i =1; i < nodes.size(); i++)
{
while(!isanc(ve.back(), nodes[i]))
{
con(ve.back(), ve[ve.size()-2]);
ve.pop_back();
}
ve.push_back(nodes[i]);
}
while(ve.size()>1)
{
con(ve.back(), ve[ve.size()-2]);
ve.pop_back();
}
return ve[0];
}
void att(int u, int p)
{
if(isx[u])
{
dp1[u] = 0;
}
else dp1[u]=1e18;
if(isy[u])
{
dp2[u] = 0;
}
else dp2[u] = 1e18;
for(auto i: g2[u])
{
if(i.first==p)continue;
att(i.first, u);
dp1[u]=min(dp1[u], dp1[i.first]+i.second);
dp2[u]=min(dp2[u], dp2[i.first]+i.second);
}
rez=min(rez, dp1[u]+dp2[u]);
}
long long Query(int S, int X[], int T, int Y[]) {
rez=1e18;
for(int i =0; i < NN; i++)
{
isx[i]=0;
isy[i]=0;
dp1[i]=1e18;
dp2[i]=1e18;
}
nodes.clear();
for(int i =0; i < S; i++) isx[X[i]]=1, nodes.push_back(X[i]);
for(int j =0; j < T; j++) isy[Y[j]]=1, nodes.push_back(Y[j]);
int x = create();
att(x, x);
return rez;
}
