#include <bits/stdc++.h>
#include "factories.h"
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;
const int SZ = 500005;
const ll INF = 1000000000000000000;
int par[SZ], lvl[SZ], sub[SZ];
ll dist[SZ][20], ans[SZ];
vector<ii> adjlist[SZ];
stack<int> st;
int dfs1(int u, int p, int l){
sub[u] = 1;
for (auto v : adjlist[u]){
if (lvl[v.fi] != -1 || v.fi == p) continue;
sub[u] += dfs1(v.fi,u,l);
}
return sub[u];
}
int dfs2(int u, int p, int n){
for (auto v : adjlist[u]){
if (lvl[v.fi] != -1 || v.fi == p) continue;
if (sub[v.fi] > n/2) return dfs2(v.fi,u,n);
}
return u;
}
void dfs3(int u, int p, int l, ll d){
//printf("dist %d %d = %lld\n",u,l,d);
dist[u][l] = d;
for (auto v : adjlist[u]){
if (lvl[v.fi] != -1 || v.fi == p) continue;
dfs3(v.fi,u,l,d+v.se);
}
}
void build(int u, int p, int l){
int n = dfs1(u,p,l);
int cent = dfs2(u,p,n);
dfs3(cent,-1,l,0);
if (p == -1) p = cent;
//printf("built %d %d %d\n",cent,p,l);
par[cent] = p;
lvl[cent] = l;
for (auto v : adjlist[cent]){
if (lvl[v.fi] != -1) continue;
build(v.fi,cent,l+1);
}
}
void update(int x){
int l = lvl[x];
int y = x;
while (l != -1){
//printf("updating %d %d: %lld\n",x,y,dist[x][l]);
ans[y] = min(ans[y],dist[x][l]);
st.push(y);
y = par[y];
l--;
}
}
ll query(int x){
ll res = INF;
int l = lvl[x];
int y = x;
while (l != -1){
//printf("at %d (level %d), nearest is %d\n",y,l,ans[y]);
res = min(res,ans[y]+dist[x][l]);
y = par[y];
l--;
}
return res;
}
void Init(int N, int A[], int B[], int D[]){
memset(ans,127,sizeof(ans));
memset(lvl,-1,sizeof(lvl));
for (int i = 0; i < N-1; i++){
adjlist[A[i]].push_back(ii(B[i],D[i]));
adjlist[B[i]].push_back(ii(A[i],D[i]));
}
build(0,-1,0);
}
ll Query(int S, int X[], int T, int Y[]){
for (int i = 0; i < S; i++){
update(X[i]);
}
ll res = INF;
for (int i = 0; i < T; i++){
res = min(res,query(Y[i]));
}
while (st.size()){
ans[st.top()] = INF;
st.pop();
}
return res;
}
