#include "factories.h"
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
using ll = long long;
int n, sz, C;
vector <vector <pair <int, ll>>> g(6e5);
vector <vector <int>> lift(6e5, vector<int>(20, 5e5));
vector <int> dep(6e5, 0);
vector <ll> dis(6e5, 0);
vector <bool> del(6e5, false);
vector <int> par(6e5, -1);
vector <ll> mn(6e5, 1e18);
queue <int> q;
void dfs(int x) {
for (auto& p : g[x]) {
ll y = p.first, w = p.second;
if (lift[x][0] == y) continue;
lift[y][0] = x;
dep[y] = dep[x] + 1;
dis[y] = dis[x] + w;
dfs(y);
}
}
int lca(int a, int b) {
if (dep[a] < dep[b]) swap(a, b);
for (int j = 19; j >= 0; j--) {
if (dep[lift[a][j]] >= dep[b]) a = lift[a][j];
}
if (a == b) return a;
for (int j = 19; j >= 0; j--) {
if (lift[a][j] == lift[b][j]) continue;
a = lift[a][j];
b = lift[b][j];
}
return lift[a][0];
}
ll dist(int a, int b) {
int c = lca(a, b);
return dis[a] + dis[b] - 2 * dis[c];
}
int get_C(int x) {
if (del[x]) return 0;
del[x] = true;
int mx = 0, sum = 1;
for (auto& p : g[x]) {
int y = p.first, cur;
cur = get_C(y);
mx = max(mx, cur);
sum += cur;
}
mx = max(mx, sz - sum);
if (mx <= sz / 2) C = x;
del[x] = false;
return sum;
}
void cd(int x, int p) {
if (del[x]) return;
sz = get_C(x);
get_C(x);
int c = C;
del[c] = true;
par[c] = p;
for (auto& p : g[c]) cd(p.first, c);
}
void Init(int N, int A[], int B[], int D[]) {
n = N;
for (int i = 0; i < n - 1; i++) {
g[A[i]].push_back({ B[i],D[i] });
g[B[i]].push_back({ A[i],D[i] });
}
dfs(0);
for (int j = 1; j < 20; j++) {
for (int i = 0; i < n; i++) {
lift[i][j] = lift[lift[i][j - 1]][j - 1];
}
}
cd(0, -1);
}
void add(int x) {
int i = x;
while (i > -1) {
mn[i] = min(mn[i], dist(x, i));
q.push(i);
i = par[i];
}
}
ll ask(int x) {
ll i = x, ret = 1e18;
while (i > -1) {
ret = min(ret, dist(x, i) + mn[i]);
i = par[i];
}
return ret;
}
ll Query(int S, int X[], int T, int Y[]) {
ll ans = 1e18;
for (int i = 0; i < T; i++) add(Y[i]);
for (int i = 0; i < S; i++) ans = min(ans, ask(X[i]));
while (q.size()) { mn[q.front()] = 1e18; q.pop(); }
return ans;
}
