#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define sc second
#define sz(v) (int)v.size()
typedef long long ll;
const int MAXN = 5*1e5+5;
const ll INF = 1e18;
vector<int> adj[MAXN];
vector<ll> w[MAXN];
vector< pair<int,ll> > anc[MAXN];
int sub[MAXN], marc[MAXN], cen;
ll ans[MAXN];
void dfsSub(int s, int p){
sub[s] = 1;
for(int viz : adj[s])
if(viz != p){
dfsSub(viz,s);
sub[s] += sub[viz];
}
}
int achaCentroid(int s, int p, int tam){
for(int viz : adj[s])
if(viz != p && !marc[viz] && sub[viz] > tam)return achaCentroid(viz,s,tam);
return s;
}
void dfs(int s, int p, ll dist){
anc[s].emplace_back(cen, dist);
for(int i = 0; i < sz(adj[s]); i++){
int viz = adj[s][i];
if(viz != p && !marc[viz])dfs(viz,s,dist+w[s][i]);
}
}
void tree(int s, int tam){
cen = achaCentroid(s,-1,tam/2);
dfs(cen,-1,0);
dfsSub(cen,-1); marc[cen] = 1;
for(int viz : adj[cen])
if(!marc[viz])tree(viz,sub[viz]);
}
void Init(int n, int a[], int b[], int d[]) {
for(int i = 0; i < n-1; i++){
adj[a[i]].push_back(b[i]); w[a[i]].push_back(d[i]);
adj[b[i]].push_back(a[i]); w[b[i]].push_back(d[i]);
}
for(int i = 0; i < n; i++)ans[i] = INF;
dfsSub(0,-1);
tree(0,n);
}
long long Query(int s, int x[], int t, int y[]) {
for(int i = 0; i < s; i++){
for(int j = 0; j < sz(anc[x[i]]); j++)
ans[anc[x[i]][j].fi] = min(ans[anc[x[i]][j].fi], anc[x[i]][j].sc);
}
ll resp = INF;
for(int i = 0; i < t; i++)
for(int j = 0; j < sz(anc[y[i]]); j++)
resp = min(resp, ans[anc[y[i]][j].fi] + anc[y[i]][j].sc);
for(int i = 0; i < s; i++)
for(int j = 0; j < sz(anc[x[i]]); j++)ans[anc[x[i]][j].fi] = INF;
return resp;
}
