#include "factories.h"
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define F first
#define S second
using namespace std;
typedef long long LL;
typedef pair<int, LL> pil;
const LL llinf=1987654321987654321;
pil arr[500010];
int n, qq, sz[500010];
vector<pil> link[500010], up[500010];
bool ch[500010];
void dfs(int num, int par){
sz[num]=1;
for(auto i:link[num]){
if(i.F==par||ch[i.F])continue;
dfs(i.F, num);
sz[num]+=sz[i.F];
}
}
int get_centroid(int num, int par, int nd){
for(auto i:link[num]){
if(!ch[i.F]&&par!=i.F&&sz[i.F]>nd)return get_centroid(i.F, num, nd);
}
return num;
}
void get_up(int rt, int num, int par, LL d){
up[num].pb(mp(rt, d));
for(auto i:link[num]){
if(i.F!=par&&!ch[i.F])get_up(rt, i.F, num, d+i.S);
}
}
void get_centroid_tree(int num){
dfs(num, 0);
int cen=get_centroid(num, 0, sz[num]/2);
get_up(cen, cen, 0, 0);
ch[cen]=true;
for(auto i:link[cen]){
if(!ch[i.F])get_centroid_tree(i.F);
}
}
void Init(int N, int A[], int B[], int D[]){
for(int i=0; i<N-1; i++){
link[A[i]+1].pb(mp(B[i]+1, D[i]));
link[B[i]+1].pb(mp(A[i]+1, D[i]));
}
get_centroid_tree(1);
}
LL Query(int S, int X[], int T, int Y[]){
qq--;
for(int i=0; i<S; i++){
for(auto j:up[X[i]+1])arr[j.F]=min(arr[j.F], mp(qq, j.S));
}
LL ret=llinf;
for(int i=0; i<T; i++){
for(auto j:up[Y[i]+1]){
if(arr[j.F].F==qq)ret=min(ret, arr[j.F].S+j.S);
}
}
return ret;
}
