#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
using P = pair<int, int>;
#define f first
#define s second
const int INF = 1e9;
static vector<vector<pair<int,int>>> adj; // adjacency list <neighbor, cost>
static vector<int> st;
static vector<int> mn;
static vector<bool> rem;
static vector<vector<pair<int,int>>> unc; // unc[v] = list of (centroid, dist)
// --- Centroid decomposition utilities ---
int sz(int nd, int pr = -1) {
st[nd] = 1;
for (auto c: adj[nd]) {
if (c.f == pr || rem[c.f]) continue;
st[nd] += sz(c.f, nd);
}
return st[nd];
}
int cen(int nd, int pr, int tot) {
for (auto c: adj[nd]) {
if (c.f == pr || rem[c.f]) continue;
if (st[c.f]*2 > tot) return cen(c.f, nd, tot);
}
return nd;
}
void calc_dist(int nd, int pr, int cent, int cdist) {
for (auto c: adj[nd]) {
if (c.f == pr || rem[c.f]) continue;
cdist += c.s;
calc_dist(c.f, nd, cent, cdist);
cdist -= c.s;
}
unc[nd].push_back({cent, cdist});
}
void build(int nd) {
int cent = cen(nd, -1, sz(nd));
for (auto c: adj[cent]) {
if (rem[c.f]) continue;
calc_dist(c.f, cent, cent, c.s);
}
rem[cent] = true;
for (auto c: adj[cent]) {
if (!rem[c.f]) build(c.f);
}
}
// --- Paint / Query helpers ---
void paint(int nd) {
for (auto x: unc[nd]) {
mn[x.f] = min(mn[x.f], x.s);
}
mn[nd] = 0;
}
void unpaint(int nd) {
for (auto x: unc[nd]) {
mn[x.f] = INF;
}
mn[nd] = INF;
}
int qry(int nd) {
int ans = mn[nd];
for (auto x: unc[nd]) {
ans = min(ans, mn[x.f] + x.s);
}
return ans;
}
// --- Required interface ---
void Init(int N, int A[], int B[], int D[]) {
adj.assign(N, {});
for (int i = 0; i < N-1; i++) {
int a = A[i];
int b = B[i];
int c = D[i];
adj[a].push_back({b,c});
adj[b].push_back({a,c});
}
st.assign(N, 0);
rem.assign(N, false);
unc.assign(N, {});
build(0);
mn.assign(N, INF);
}
long long Query(int S, int X[], int T, int Y[]) {
// Paint all nodes in Y
for (int i = 0; i < T; i++) {
paint(Y[i]);
}
int ans = INF;
for (int i = 0; i < S; i++) {
ans = min(ans, qry(X[i]));
}
// Unpaint nodes in Y
for (int i = 0; i < T; i++) {
unpaint(Y[i]);
}
return ans;
}
