#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
#include "factories.h"
#include<bits/stdc++.h>
#define ll long long
#define F first
#define S second
using namespace std;
ll dis[500005];
bool vis[500005];
vector<pair<int,ll>>adj[500005];
vector<pair<int,ll>>cen[500005];
ll sz[500005];
void dfssz(int u,int p)
{
//cout<<u<<" "<<p<<endl;
if(vis[u])return;
sz[u]=1;
for(auto x:adj[u])
{
if(x.F==p)continue;
dfssz(x.F,u);
sz[u]+=sz[x.F];
}
}
int getcen(int u,int p,int s)
{
//if(vis[u])return 0;
int cent=u;
for(auto x:adj[u])
{
if(x.F==p||vis[x.F])continue;
if(sz[x.F]*2>s)
cent=getcen(x.F,u,s);
}
return cent;
}
void dfscen(int u,int p,ll d,int t)
{
if(vis[u])return;
cen[u].push_back({t,d});
for(auto x:adj[u])
{
if(x.F==p)continue;
dfscen(x.F,u,x.S+d,t);
}
}
void decompose(int u,int p)
{
//cout<<u<<endl;
dfssz(u,0);
//cout<<u<<endl;
int cent=getcen(u,p,sz[u]);
//cout<<cent<<endl;
dfscen(cent,0,0,cent);
vis[cent]=1;
for(auto x:adj[cent])
{
if(vis[x.F])continue;
decompose(x.F,cent);
}
}
void Init(int N, int A[], int B[], int D[]) {
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]});
}
decompose(1,0);
}
long long Query(int S, int X[], int T, int Y[]) {
ll ans=1e18;
for(int i=0;i<S;i++)
{
//cout<<X[i]<<" ";
for(auto u:cen[++X[i]])
{
dis[u.F]=1e18;
}
}
for(int i=0;i<T;i++)
{
for(auto u:cen[++Y[i]])
{
dis[u.F]=1e18;
}
}
//cout<<endl;
for(int i=0;i<S;i++)
{
for(auto u:cen[X[i]])
{
dis[u.F]=min(dis[u.F],u.S);
//cout<<X[i]<<" "<<u.F<<" "<<u.S<<endl;
}
}
for(int i=0;i<T;i++)
{
for(auto u:cen[Y[i]])
{
ans=min(ans,dis[u.F]+u.S);
//cout<<Y[i]<<" "<<u.F<<" "<<dis[u.F]<<endl;
}
}
return ans;
}
