#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;
int n, q, siz[500010], d[500010], sparse[500010][30], centpar[500010];
vector<pil> link[500010];
bool ch[500010];
LL dep[500010];
void dfs(int num, int par){
siz[num]=1;
d[num]=d[par]+1;
sparse[num][0]=par;
for(auto i:link[num]){
if(i.F==par)continue;
dep[i.F]=dep[num]+i.S;
dfs(i.F, num);
siz[num]+=siz[i.F];
}
}
int lca(int x, int y){
if(d[x]>d[y])swap(x, y);
for(int i=20; i>=0; i--){
if(d[y]-d[x]>=(1<<i))y=sparse[y][i];
}
if(x==y)return x;
for(int i=20; i>=0; i--){
if(sparse[x][i]!=sparse[y][i]){
x=sparse[x][i];
y=sparse[y][i];
}
}
return sparse[x][0];
}
inline LL dist(int x, int y){return dep[x]+dep[y]-2*dep[lca(x, y)];}
int get_centroid(int num, int par, int sz){
bool flag=true;
for(auto i:link[num]){
if(ch[i.F])continue;
if(siz[i.F]>sz/2)flag=false;
}
if(flag)return num;
for(auto i:link[num]){
if(i.F==par||ch[i.F])continue;
int temp=siz[i.F];
siz[num]=sz-siz[i.F];
siz[i.F]=sz;
int ret=get_centroid(i.F, num, sz);
if(ret)return ret;
siz[num]=sz;
siz[i.F]=temp;
}
return 0;
}
void make_centroidtree(int num, int par){
int cen=get_centroid(num, 0, siz[num]);
ch[cen]=true;
centpar[cen]=par;
for(auto i:link[cen]){
if(ch[i.F])continue;
make_centroidtree(i.F, cen);
}
}
pil arr[500010];
vector<pil> up[500010];
void Init(int N, int A[], int B[], int D[]){
n=N;
for(int i=0; i<n-1; i++){
int a=A[i];
int b=B[i];
LL c=(LL)D[i];
link[a+1].pb(mp(b+1, c));
link[b+1].pb(mp(a+1, c));
}
dfs(1, 0);
for(int j=1; j<=20; j++){
for(int i=1; i<=n; i++){
sparse[i][j]=sparse[sparse[i][j-1]][j-1];
}
}
make_centroidtree(1, 0);
for(int i=1; i<=n; i++){
int now=i;
while(now){
up[i].pb(mp(now, dist(i, now)));
now=centpar[now];
}
}
}
int qq=0;
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)break;
ret=min(ret, arr[j.F].S+j.S);
}
}
return ret;
}
