#include <bits/stdc++.h>
#include "factories.h"
#define ll long long
#define pb push_back
#define endl "\n"
using namespace std;
ll n;
vector<ll> subtree_size,min_dist;
vector<vector<pair<ll,ll>>> adj,anc;
vector<bool> del;
inline ll get_subtree(ll node, ll parent){
subtree_size[node] = 1;
for(auto go : adj[node]){
if(del[go.first] or go.first == parent) continue;
subtree_size[node] += get_subtree(go.first,node);
}
return subtree_size[node];
}
inline ll get_centroid(ll node, ll parent, ll tree_size){
for(auto go : adj[node]){
if(del[go.first] or go.first == parent) continue;
if(subtree_size[go.first] * 2 > tree_size){
return get_centroid(go.first,node,tree_size);
}
}
return node;
}
inline void get_dist(ll node,ll centroid, ll parent,ll dist){
for(auto go : adj[node]){
if(del[go.first] or go.first == parent) continue;
get_dist(go.first,centroid,node,dist + go.second);
}
anc[node].pb({centroid,dist});
}
inline void centroid_decomp(ll centroid){
centroid = get_centroid(centroid,-1,get_subtree(centroid,-1));
for(auto go : adj[centroid]){
if(del[go.first]) continue;
get_dist(go.first,centroid,centroid,go.second);
}
del[centroid] = 1;
for(auto go : adj[centroid]){
if(del[go.first]) continue;
centroid_decomp(go.first);
}
}
void Init(int N, int A[], int B[], int D[]){
n = N;
adj.resize(n);
anc.resize(n);
subtree_size.resize(n);
del.resize(n,0);
min_dist.resize(n);
for(ll i = 0 ; i < n-1 ; i++){
adj[A[i]].pb({B[i],D[i]});
adj[B[i]].pb({A[i],D[i]});
}
centroid_decomp(0);
}
long long Query(int S, int X[], int T, int Y[]){
fill(min_dist.begin(),min_dist.end(),1e15);
for(ll i = 0 ; i < S ; i++){
for(auto it : anc[X[i]]){
min_dist[it.first] = min(min_dist[it.first], it.second);
}
min_dist[X[i]] = 0;
}
ll ret = 1e15;
for(ll i = 0 ; i < T ; i++){
ret = min(ret,min_dist[Y[i]]);
for(auto it : anc[Y[i]]){
ret = min(ret,min_dist[it.first] + it.second);
}
}
return ret;
}
