#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;
ll dis[maxn], sparse[maxn][20];
int depth[maxn];
void dfs(int x, int p, ll c){
dis[x] = c;
depth[x] = depth[p] + 1;
sparse[x][0] = p;
for(auto i : edges[x]){
if(i.first != p){
dfs(i.first, x, c + i.second);
}
}
}
void build_lca(){
for(int j = 1; j < 20; ++j){
for(int i = 1; i <= n; ++i){
if(sparse[i][j - 1] != 0){
sparse[i][j] = sparse[sparse[i][j - 1]][j - 1];
}
}
}
}
int LCA(int x, int y){
if(depth[x] < depth[y])swap(x, y);
for(int i = 19; i >= 0; --i){
if(depth[x] - (1 << i) >= depth[y]){
x = sparse[x][i];
}
}
if(x == y)return x;
for(int i = 19; i >= 0; --i){
if(sparse[x][i] != sparse[y][i] && sparse[x][i] != 0 && sparse[y][i] != 0){
x = sparse[x][i];
y = sparse[y][i];
}
}
return sparse[x][0];
}
ll DIS(int x, int y){
return dis[x] + dis[y] - (2 * dis[LCA(x, y)]);
}
int sub[maxn], par[maxn], cent_dep[maxn];
int cent_vis[maxn];
void dfs(int x, int p){
sub[x] = 1;
for(auto i : edges[x]){
if(i.first != p){
if(!cent_vis[i.first]){
dfs(i.first, x);
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);
int c = find_centroid(x, 0, sub[x] / 2);
par[c] = p;
cent_vis[c] = 1;
cent_dep[c] = d;
for(auto i : edges[c]){
if(!cent_vis[i.first]){
build(i.first, c, d + 1);
}
}
cent_vis[c] = 0;
}
ll mn[maxn], cent_dis[maxn][20];
void calc(int x){
int cur = x, lvl = 0;
while(cur != 0){
cent_dis[x][lvl] = DIS(cur, x);
cur = par[cur];
++lvl;
}
}
stack<int> st;
void upd(int x){
int cur = x;
while(cur != 0){
mn[cur] = min(mn[cur], cent_dis[x][cent_dep[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[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]});
}
dfs(1, 1, 0);
build_lca();
build(1, 0, 1);
for(int i = 1; i <= N; ++i){
calc(i);
}
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;
}
