#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
#define pb push_back
#define mp make_pair
const int NN = 5e5+7;
vector <vector <pii>> graph(NN);
vector <vector <ll>> dist(NN, vector <ll> (20));
vector <int> saizu(NN), par(NN), vis(NN), lvl(NN);
vector <ll> ans(NN, 2e18);
int timer;
stack <int> st;
void find_size(int v, int p, int l){
saizu[v] = 1;
for(auto to : graph[v]){
if(!vis[to.first] && to.first != p){
if(l) dist[to.first][l-1] = dist[v][l-1]+to.second;
find_size(to.first, v, l);
saizu[v] += saizu[to.first];
}
}
}
int find_centroid(int v, int p, int n){
for(auto to : graph[v]){
if(!vis[to.first] && to.first != p && saizu[to.first] > n/2){
return find_centroid(to.first, v, n);
}
}
return v;
}
void init_centroid(int v = 0, int p = -1, int l = 0){
find_size(v, -1, l);
int c = find_centroid(v, p, saizu[v]);
vis[c] = 1;
par[c] = p;
lvl[c] = l;
for(auto to : graph[c]){
if(!vis[to.first]){
dist[to.first][l] = to.second;
init_centroid(to.first, c, l+1);
}
}
vis[c] = 0;
}
void Init(int n, int x[], int y[], int w[]){
for(int i = 0; i < n-1; i++){
graph[x[i]].pb(mp(y[i], w[i]));
graph[y[i]].pb(mp(x[i], w[i]));
}
init_centroid();
}
void update(int v){
int x = v, l = lvl[v];
while(x != -1){
ans[x] = min(ans[x], dist[v][l]);
st.push(x);
x = par[x];
l--;
}
}
ll get(int v){
ll x = v, mn = 2e18, l = lvl[v];
while(x != -1){
mn = min(ans[x]+dist[v][l], mn);
x = par[x];
l--;
}
return mn;
}
long long Query(int s, int x[], int t, int y[]){
ll mn = 2e18;
for(int i = 0; i < s; i++)
update(x[i]);
for(int i = 0; i < t; i++)
mn = min(mn, get(y[i]));
while(st.size()){
ans[st.top()] = 2e18;
st.pop();
}
return mn;
}
