#include<bits/stdc++.h>
#include "factories.h"
#define ll long long
#define pll pair<ll,ll>
using namespace std;
vector<vector<pll>> e;
vector<vector<pll>> anc;
vector<ll> sz,dist;
vector<bool> rem;
ll getsz(ll u,ll p){
sz[u]=1;
for(auto v:e[u]){
if(v.first==p or rem[v.first]) continue;
sz[u]+=getsz(v.first,u);
}
return sz[u];
}
ll getct(ll u,ll p,ll n){
for(auto v:e[u]){
if(v.first==p or rem[v.first]) continue;
if(sz[v.first]>n/2) return getct(v.first,u,n);
}
return u;
}
void getdist(ll u,ll p,ll ct,ll d){
anc[u].push_back({ct,d});
for(auto v:e[u]){
if(v.first==p or rem[v.first]) continue;
getdist(v.first,u,ct,d+v.second);
}
}
void decompose(ll u){
getsz(u,u);
ll ct=getct(u,u,sz[u]);
rem[ct]=1;
for(auto v:e[ct]){
if(rem[v.first]) continue;
getdist(v.first,ct,ct,v.second);
}
for(auto v:e[ct]){
if(rem[v.first]) continue;
decompose(v.first);
}
}
void Init(int n, int A[], int B[], int D[]){
e.resize(n+1);
rem.resize(n+1,0);
sz.resize(n+1);
dist.resize(n+1,1e18);
anc.resize(n+1);
for(ll i=0 ; i<n-1 ; i++){
e[A[i]].push_back({B[i],D[i]});
e[B[i]].push_back({A[i],D[i]});
}
decompose(0);
}
long long Query(int S, int X[], int T, int Y[]){
ll ans=1e18;
int i;
for(i=0 ; i<T ; i++){
for(auto v:anc[Y[i]]){
dist[v.first]=1e18;
}
}
for(i=0 ; i<S ; i++){
for(auto v:anc[X[i]]){
dist[v.first]=min(dist[v.first],v.second);
}
}
for(i=0 ; i<T ; i++){
for(auto v:anc[Y[i]]){
ans=min(ans,dist[v.first]+v.second);
}
}
return ans;
}
