#include "factories.h"
#include "bits/stdc++.h"
using namespace std;
const int maxn = 500005;
using ll = long long;
const ll inf = 1e18;
vector<pair<int, ll>> edges[maxn];
int n;
int sub[maxn], par[maxn], cent_dep[maxn];
int cent_vis[maxn];
ll mn[maxn], cent_dis[maxn][20];
stack<int> st;
void dfs(int x, int p, int d){
sub[x] = 1;
for(auto i : edges[x]){
if(i.first != p){
if(!cent_vis[i.first]){
if(d){
cent_dis[i.first][d - 1] = cent_dis[x][d - 1] + i.second;
}
dfs(i.first, x, d);
sub[x] += sub[i.first];
}
}
}
}
int find_centroid(int x, int p, int range){
for(auto i : edges[x]){
if(i.first != p && !cent_vis[i.first]){
if(sub[i.first] > range)return find_centroid(i.first, x, range);
}
}return x;
}
void build(int x, int p, int d){
dfs(x, -1, d);
int c = find_centroid(x, -1, sub[x] / 2);
par[c] = p;
cent_vis[c] = 1;
cent_dep[c] = d;
for(auto i : edges[c]){
if(!cent_vis[i.first]){
cent_dis[i.first][d] = i.second;
build(i.first, c, d + 1);
}
}
cent_vis[c] = 0;
}
void upd(int x){
int cur = x;
while(cur != 0){
mn[cur] = min(mn[cur], cent_dis[x][cent_dep[cur]]);
st.push(cur);
cur = par[cur];
}
}
ll query(int x){
ll ret = mn[x];
int cur = x;
while(cur != 0){
ret = min(ret, mn[cur] + cent_dis[x][cent_dep[cur]]);
cur = par[cur];
}
return ret;
}
void Init(int N, int A[], int B[], int D[]) {
n = N;
for(int i = 0; i < N - 1; ++i){
edges[A[i] + 1].push_back({B[i] + 1, D[i]});
edges[B[i] + 1].push_back({A[i] + 1, D[i]});
}
build(1, 0, 0);
for(int i = 1; i <= N; ++i){
mn[i] = inf;
}
}
long long Query(int S, int X[], int T, int Y[]) {
for(int i = 0; i < S; ++i){
upd(X[i] + 1);
}
ll ans = inf;
for(int i = 0; i < T; ++i){
ans = min(ans, query(Y[i] + 1));
}
while(!st.empty()){
mn[st.top()] = inf;
st.pop();
}
return ans;
}
