#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 5e5;
const ll INF = 1e18;
int N;
vector<pii> adj[MAXN+10];
int sz[MAXN+10], del[MAXN+10], cenpar[MAXN+10], cendep[MAXN+10];
ll dist[MAXN+10][30];
void getsz(int now, int bef)
{
sz[now]=1;
for(auto &nxt : adj[now])
{
if(nxt.first==bef) continue;
if(del[nxt.first]) continue;
getsz(nxt.first, now);
sz[now]+=sz[nxt.first];
}
}
int getcen(int now, int bef, int S)
{
for(auto &nxt : adj[now])
{
if(nxt.first==bef) continue;
if(del[nxt.first]) continue;
if(sz[nxt.first]>S/2) return getcen(nxt.first, now, S);
}
return now;
}
void dfs(int now, int bef, ll d, int cdep)
{
dist[now][cdep]=d;
for(auto &nxt : adj[now])
{
if(nxt.first==bef) continue;
if(del[nxt.first]) continue;
dfs(nxt.first, now, d+nxt.second, cdep);
}
}
void decomp(int now, int cdep, int bef)
{
getsz(now, now);
now=getcen(now, now, sz[now]);
cendep[now]=cdep;
cenpar[now]=bef;
dfs(now, now, 0, cdep);
del[now]=true;
for(auto &nxt : adj[now])
{
if(del[nxt.first]) continue;
decomp(nxt.first, cdep+1, now);
}
}
ll A[MAXN+10], B[MAXN+10];
void Init(int _N, int AA[], int BB[], int D[])
{
int i, j;
N=_N;
for(i=0; i<N-1; i++)
{
int u=AA[i]+1, v=BB[i]+1, w=D[i];
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
decomp(1, 1, 0);
for(i=1; i<=N; i++) A[i]=B[i]=INF;
}
ll Query(int S, int X[], int T, int Y[])
{
int i, j;
vector<int> V;
for(i=0; i<S; i++)
{
int now=X[i]+1, u=X[i]+1;
while(now)
{
A[now]=min(A[now], dist[u][cendep[now]]);
V.push_back(now);
now=cenpar[now];
}
}
for(i=0; i<T; i++)
{
int now=Y[i]+1, u=Y[i]+1;
while(now)
{
B[now]=min(B[now], dist[u][cendep[now]]);
V.push_back(now);
now=cenpar[now];
}
}
ll ans=INF;
for(auto it : V) ans=min(ans, A[it]+B[it]);
for(auto it : V) A[it]=B[it]=INF;
return ans;
}
