#include<bits/stdc++.h>
#include "factories.h"
using namespace std;
typedef long long LL;
const int N=(int)1e6;
const int MAXLOG=19;
const LL INF=1e18+7;
vector<pair<int,int>>ke[N+2];
#define fi first
#define se second
void add_canh(int u,int v,int c){
ke[u].push_back({v,c}),ke[v].push_back({u,c});
return;
}
int par[N+2][MAXLOG+2];
int h[N+2];
LL d[N+2];
void pre_dfs(int u,int p){
h[u]=h[p]+1;
par[u][0]=p;
for(int i=1;i<=MAXLOG;++i)
par[u][i]=par[par[u][i-1]][i-1];
for(auto&v:ke[u]){
if (v.fi==p) continue;
d[v.fi]=d[u]+v.se;
pre_dfs(v.fi,u);
}
return;
}
int LCA(int u,int v){
if (h[u]<h[v]) swap(u,v);
for(int i=MAXLOG;i>=0;--i){
if (h[par[u][i]]>=h[v])
u=par[u][i];
}
if (u==v) return u;
for(int i=MAXLOG;i>=0;--i){
if (par[u][i]!=par[v][i]){
u=par[u][i],v=par[v][i];
}
}
return par[u][0];
}
LL getdist(int u,int v){
int lca=LCA(u,v);
return d[u]+d[v]-d[lca]*2;
}
class Centroid{
private:
vector<int>par,sub;
vector<LL>mx;
public:
vector<int>used;
vector<bool>del;
void init_size(int _n){
par.resize(_n+2,0);
sub.resize(_n+2,0);
del.resize(_n+2,0);
mx.resize(_n+2,INF);
}
void dfs(int u,int p){
sub[u]=1;
for(auto&v:ke[u]){
if (v.fi==p || del[v.fi]) continue;
dfs(v.fi,u);
sub[u]+=sub[v.fi];
}
}
int Find_centroid(int u,int p,int half){
for(auto&v:ke[u]){
if (del[v.fi] || v.fi==p) continue;
if (sub[v.fi]>half) return Find_centroid(v.fi,u,half);
}
return u;
}
void build_centroid(int u,int p){
dfs(u,u);
u=Find_centroid(u,u,sub[u]/2);
del[u]=true;
par[u]=p;
for(auto&v:ke[u]) if (del[v.fi]==0) build_centroid(v.fi,u);
}
void add(int u){
int cur=u;
while (cur!=0){
mx[cur]=min(mx[cur],getdist(u,cur));
if (del[cur]==0) del[cur]=true,used.push_back(cur);
cur=par[cur];
}
}
void era(){
for(auto&x:used) mx[x]=INF,del[x]=false;
}
LL Find(int u){
int cur=u;
LL ans=INF;
while (cur!=0){
ans=min(ans,getdist(cur,u)+mx[cur]);
cur=par[cur];
}
return ans;
}
};
Centroid tree;
void Init(int n,int a[],int b[],int d[]){
for(int i=0;i<n-1;++i){
++a[i],++b[i];
add_canh(a[i],b[i],d[i]);
}
pre_dfs(1,0);
tree.init_size(n);
tree.build_centroid(1,0);
tree.del.assign(n+2,false);
return;
}
long long Query(int s,int x[],int t,int y[]){
LL ans=INF;
for(int i=0;i<s;++i) ++x[i];
for(int i=0;i<t;++i) ++y[i];
for(int i=0;i<s;++i) tree.add(x[i]);
for(int i=0;i<t;++i) ans=min(ans,tree.Find(y[i]));
tree.era();
return ans;
}
