#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];
multiset<int> ms[MAXN];
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]){
if(x == 1){
ms[c].insert(d);
} else ms[c].erase(ms[c].find(d));
}
}
ll query(int v){
ll r = INF;
for(auto [c, d] : ancestors[v]){
if(!ms[c].empty()){
r = min(r, d + *ms[c].begin());
}
}
return r;
}
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], 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], 1);
ll ans = INF;
for(int i=0; i<t; i++) ans = min(ans, query(y[i]));
for(int i=0; i<s; i++) paint(x[i], -1);
return ans;
}
