#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
#define mp make_pair
#define pb push_back
int n;
vector<pair<int,int> > adj[500001];
int sub[500001],lvl[500001],par[500001];
long long ans[500001];
long long dist[500001][19];
stack<int> st;
int dfs1(int u,int p,int l){
sub[u]=1; // Subtree size is 1
for (auto i:adj[u]){
if (lvl[i.first]!=-1) continue;
// Already added to centroid tree
if (i.first==p) continue;
if (l>0) dist[i.first][l-1]=dist[u][l-1]+i.second;
sub[u]+=dfs1(i.first,u,l);
// Increase size of subtree
}
return sub[u];
}
int dfs2(int u,int p,int sn){
// Pass in the size of the subtree
for (auto i:adj[u]){
if (lvl[i.first]!=-1) continue;
// Already added to centroid tree
if (i.first==p) continue;
if (sub[i.first]>sn/2){
return dfs2(i.first,u,sn);
}
}
return u; // No child has size more than n/2 , hence you are the centroid
}
// Building from node u, with a parent p and level l
void build(int u,int p,int l){
int cn=dfs1(u,p,l);
int cent=dfs2(u,p,cn);
if (p==-1) p=cent;
par[cent]=p;
lvl[cent]=l;
for (auto i:adj[cent]){
if (lvl[i.first]!=-1) continue;
dist[i.first][l]=i.second;
build(i.first,cent,l+1);
}
}
void upd(int x){
int l=lvl[x];
int y=x;
while (l!=-1){
ans[y]=min(ans[y],dist[x][l]);
// Check the shortest distance against the distance between the current node
st.push(y);
y=par[y];
// Traverse up the centroid tree
l--;
// Keep track of which parent we are on
}
}
long long qry(int x){
long long res=1e16;
int l=lvl[x];
int y=x;
while (l!=-1){
res=min(res,ans[y]+dist[x][l]);
y=par[y];
l--;
}
return res;
}
void Init(int N, int A[], int B[], int D[]) {
n=N;
for (int i=0;i<n-1;i++){
adj[A[i]].pb(mp(B[i],D[i]));
adj[B[i]].pb(mp(A[i],D[i]));
}
memset(lvl,-1,sizeof(lvl));
build(0,-1,0);
for (int i=0;i<n;i++) ans[i]=1e16;
}
long long Query(int S, int X[], int T, int Y[]) {
for (int i=0;i<S;i++) upd(X[i]);
long long res=1e16;
for (int i=0;i<T;i++) res=min(res,qry(Y[i]));
while (!st.empty()){
ans[st.top()]=1e16;
st.pop();
}
return res;
}
