#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
const int N = 500500;
const long long inf = 1e18;
int sub[N], pos[N];
long long dis[N], mn[N];
vector<int> modify;
vector<pair<int, long long>> par[N];
vector<pair<int, int>> adj[N];
void dfs (int u, int p = 0){
sub[u] = 1;
for (auto [v, d] : adj[u]){
if (v != p && pos[v] == 0){
dfs(v, u);
sub[u] += sub[v];
}
}
}
void dfs2 (int u, int p, int root, long long dep){
par[u].push_back({root, dep});
for (auto [v, d] : adj[u]){
if (v != p && pos[v] == 0){
dfs2(v, u, root, dep + 1ll * d);
}
}
return;
}
int centroid (int u, int p, int n){
for (auto [v, d] : adj[u]){
if (v != p && pos[v] == 0 && sub[v] * 2 > n){
return centroid(v, u, n);
}
}
return u;
}
void buildCentroid (int u, int p){
pos[u] = 1;
dfs(u);
dfs2(u, 0, u, 0);
vector<int> nxt;
for (auto [v, d] : adj[u]){
if (pos[v] == 0 && v != p){
int nr = centroid(v, u, sub[v]);
nxt.push_back(nr);
}
}
for (int r : nxt){
buildCentroid(r, u);
}
return;
}
void Init (int n, int a[], int b[], int d[]){
fill(mn, mn + N, inf);
fill(pos, pos + N, 0);
for (int i = 0; i < n - 1; ++i){
++a[i]; ++b[i];
adj[a[i]].push_back({b[i], d[i]});
adj[b[i]].push_back({a[i], d[i]});
}
dfs(1);
int root = centroid(1, 0, n);
buildCentroid(root, root);
// for (int i = 1; i <= n; ++i){
// cout << i << " " << par[i].first << " " << par[i].second << "\n";
// }
return;
}
void upd (int u){
for (auto [v, d] : par[u]){
modify.push_back(v);
mn[v] = min(mn[v], d);
}
return;
}
long long get (int u){
long long ans = inf;
for (auto [v, d] : par[u]){
ans = min(ans, mn[v] + d);
}
return ans;
}
long long Query (int S, int X[], int T, int Y[]){
for (int i = 0; i < S; ++i){
++X[i];
upd(X[i]);
}
long long ans = inf;
for (int i = 0; i < T; ++i){
++Y[i];
ans = min(ans, get(Y[i]));
}
for (int u : modify){
mn[u] = inf;
}
modify.clear();
return ans;
}
