#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
constexpr int N = 5e5 + 5;
constexpr long long inf = 1e18;
vector<pair<int, int>> g[N];
int sz[N];
bool deleted[N];
void dfs_size(int u, int p) {
sz[u] = 1;
for (auto [v, w] : g[u]) {
if (v != p && !deleted[v]) {
dfs_size(v, u);
sz[u] += sz[v];
}
}
}
int find_centroid(int u, int p, int n) {
for (auto [v, w] : g[u]) {
if (v != p && !deleted[v] && sz[v] * 2 > n) {
return find_centroid(v, u, n);
}
}
return u;
}
map<int, long long> down[N];
vector<pair<int, long long>> f[N];
void dfs(int u, int p, long long d, int c) {
f[u].push_back({c, d});
assert(f[u].size() <= 20);
if (!down[c].count(u)) {
down[c][u] = d;
} else {
down[c][u] = min(down[c][u], d);
}
for (auto [v, w] : g[u]) {
if (!deleted[v] && v != p) {
dfs(v, u, d + w, c);
}
}
}
void go(int u) {
dfs_size(u, -1);
int r = find_centroid(u, -1, sz[u]);
deleted[r] = 1;
dfs(r, -1, 0, r);
for (auto [v, w] : g[r]) {
if (!deleted[v]) {
go(v);
}
}
}
map<int, long long> dp;
void Init(int N, int A[], int B[], int D[]) {
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]});
}
go(0);
}
long long Query(int S, int X[], int T, int Y[]) {
dp.clear();
for (int i = 0; i < S; i++) {
int u = X[i];
for (auto [c, d] : f[u]) {
if (!dp.count(c)) {
dp[c] = d;
} else {
dp[c] = min(dp[c], d);
}
}
}
long long ans = inf;
for (int i = 0; i < T; i++) {
int u = Y[i];
for (auto [c, d] : f[u]) {
if (dp.count(c)) {
ans = min(ans, dp[c] + d);
}
}
}
return ans;
}
