#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
using ll = long long;
const int MAXN = 5e5 + 10;
const ll INF = 1e18;
int used[MAXN], sub[MAXN];
ll dist[MAXN];
vector<pair<int, ll>> adj[MAXN], ancestors[MAXN];
pair<ll, ll> min_dist[MAXN];
int q = 0;
int get_size(int v, int p){
sub[v] = 1;
for(auto [u, w] : adj[v]){
if(used[u] || u == p) continue;
sub[v] += get_size(u, v);
}
return sub[v];
}
int get_centroid(int v, int p, int sz){
for(auto [u, w] : adj[v]){
if(used[u] || u == p) continue;
if(sub[u] > sz / 2) return get_centroid(u, v, sz);
}
return v;
}
void get_dists(int v, int p, int c){
for(auto [u, w] : adj[v]){
if(used[u] || u == p) continue;
dist[u] = dist[v] + w;
get_dists(u, v, c);
}
ancestors[v].push_back({c, dist[v]});
}
void build(int v, int p){
int c = get_centroid(v, p, get_size(v, p));
used[c] = 1;
dist[c] = 0;
get_dists(c, c, c);
for(auto [u, w] : adj[c]){
if(used[u]) continue;
build(u, c);
}
}
void paint(int v, int x){
for(auto [c, d] : ancestors[v]){
min_dist[c] = min(min_dist[c], {-x, d});
}
}
ll query(int v){
pair<ll, ll> r = {INF, INF};
for(auto [c, d] : ancestors[v]){
r = min(r, {min_dist[c].first, d + min_dist[c].second});
}
return r.second;
}
void Init(int n, int a[], int b[], int d[]){
for(int i=0; i<n; i++) min_dist[i] = {INF, INF};
for(int i=0; i<(n - 1); i++){
adj[a[i]].push_back({b[i], d[i]});
adj[b[i]].push_back({a[i], d[i]});
}
build(0, 0);
}
ll Query(int s, int x[], int t, int y[]){
for(int i=0; i<s; i++) paint(x[i], q);
q ++;
ll ans = INF;
for(int i=0; i<t; i++) ans = min(ans, query(y[i]));
return ans;
}
