#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
using ll = long long;
using pii = pair<int, ll>;
vector<bool> removed;
vector<vector<pii>> cd;
vector<vector<pii>> adj;
vector<int> sz;
vector<ll> dist;
int dfs(int n, int p=-1) {
sz[n] = 1;
for (auto x : adj[n]) {
if (x.first==p || removed[x.first]) continue;
sz[n] += dfs(x.first, n);
}
return sz[n];
}
int centroid(int u, int n, int p=-1) {
for (auto x : adj[u]) {
if (x.first == p || removed[x.first]) continue;
if (sz[x.first]*2 > n) return centroid(x.first, n, u);
}
return u;
}
void upd(int n, int c, ll dis, int p=-1) {
cd[n].push_back({c, dis});
for (auto x : adj[n]) {
if (x.first == p || removed[x.first]) continue;
upd(x.first, c, dis+x.second, n);
}
}
void build(int u) {
int n=dfs(u);
int c = centroid(u, n);
removed[c] = true;
upd(c, c, 0);
for (auto x : adj[c]) {
if (removed[x.first]) continue;
build(x.first);
}
}
void Init(int N, int A[], int B[], int D[]) {
adj.assign(N, {});
cd.assign(N, {});
removed.assign(N, false);
sz.assign(N, 0);
for (int i=0; i<N-1; i++) {
int a = A[i];
int b = B[i];
adj[a].push_back({b, D[i]});
adj[b].push_back({a, D[i]});
}
build(0);
dist.assign(N, 1e18);
}
long long Query(int S, int X[], int T, int Y[]) {
for (int i=0;i<T; i++) {
for (auto x : cd[Y[i]]) {
dist[x.first] = 1e18;
}
}
for (int i=0; i<S; i++) {
for (auto x : cd[X[i]]) {
dist[x.first] = min(dist[x.first], x.second);
}
}
ll ans = 1e18;
for (int i=0; i<T; i++) {
for (auto x : cd[Y[i]]) {
ans = min(ans, dist[x.first]+x.second);
}
}
return ans;
}
