#include <bits/stdc++.h>
#include "factories.h"
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast,unroll-loops")
using namespace std;
#define ll long long
const ll MXN = 500005, INF = 1e18;
bool done[MXN];
int sz[MXN], cen[MXN], temp[MXN];
ll dist[MXN][20], ans[MXN];
vector<pair<int, ll>> g[MXN];
int getSize(int cur, int par = -1) {
sz[cur] = 1;
for (auto [next, cost] : g[cur]) {
if (next != par && !done[next]) sz[cur] += getSize(next, cur);
}
return sz[cur];
}
int getCentroid(int cur, int des, int par = -1) {
for (auto [next, cost] : g[cur]) {
if (next != par && !done[next] && sz[next] > des / 2) return getCentroid(next, des, cur);
}
return cur;
}
void solve(int cur, int par, int top, ll dis) {
dist[cur][temp[cur]++] = dis;
for (auto [next, cost] : g[cur]) {
if (next != par && !done[next]) {
cen[next] = top;
solve(next, cur, top, dis + cost);
}
}
}
void decomp(int cur) {
cur = getCentroid(cur, getSize(cur));
done[cur] = 1;
solve(cur, cur, cur, 0);
for (auto [next, cost] : g[cur]) {
if (!done[next]) decomp(next);
}
}
void update(int cur, int t = 1) {
for (int Cur = cur, ind = temp[cur] - 1; Cur >= 0; Cur = cen[Cur], ind--) {
if (t) ans[Cur] = min(ans[Cur], dist[cur][ind]);
else ans[Cur] = INF;
}
}
ll query(int cur) {
ll mn = INF;
for (int Cur = cur, ind = temp[cur] - 1; Cur >= 0; Cur = cen[Cur], ind--) {
mn = min(mn, ans[Cur] + dist[cur][ind]);
}
return mn;
}
void Init(int N, int A[], int B[], int D[]) {
for (int i = 0; i < N; i++) {
ans[i] = INF;
cen[i] = -1;
for (int j = 0; j < 20; j++) dist[i][j] = INF;
if (i == N - 1) break;
g[A[i]].push_back({B[i], D[i]});
g[B[i]].push_back({A[i], D[i]});
}
decomp(0);
}
ll Query(int S, int X[], int T, int Y[]) {
for (int i = 0; i < S; i++) update(X[i]);
ll mn = INF;
for (int i = 0; i < T; i++) mn = min(mn, query(Y[i]));
for (int i = 0; i < S; i++) update(X[i], 0);
return mn;
}
