#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
#define dbg(x) cerr << #x << ": " << x << endl;
const int MAX_N = 500'000;
const int MAX_LOG = 20;
const long long INF = 1e16;
vector<pair<int, int>> g[MAX_N];
int sz[MAX_N];
int level[MAX_N];
bool used[MAX_N];
long long dist[MAX_LOG][MAX_N];
vector<int> centroids[MAX_N];
multiset<long long> distances[MAX_N];
void dfs_calc(int v, int p, int curr_weight, int c) {
sz[v] = 1;
if (c != -1) {
dist[level[c]][v] = dist[level[c]][p] + curr_weight;
centroids[v].push_back(c);
}
for (const auto& [u, weight] : g[v]) {
if (used[u] || u == p) continue;
dfs_calc(u, v, weight, c);
sz[v] += sz[u];
}
}
int find_centroid(int v, int p, int n) {
for (const auto& [u, w] : g[v]) {
if (used[u] || u == p) continue;
if (2 * sz[u] > n) {
return find_centroid(u, v, n);
}
}
return v;
}
void dfs_build(int v = 0, int p = -1, int curr_weight = -1) {
dfs_calc(v, p, curr_weight, p);
int c = find_centroid(v, -1, sz[v]);
if (p != -1) level[c] = level[p] + 1;
centroids[c].push_back(c);
used[c] = true;
for (const auto& [u, weight] : g[c]) {
if (!used[u]) {
dfs_build(u, c, weight);
}
}
}
void add_vertex(int v) {
for (int c : centroids[v]) {
distances[c].insert(dist[level[c]][v]);
}
}
void remove_vertex(int v) {
for (int c : centroids[v]) {
distances[c].erase(distances[c].find(dist[level[c]][v]));
}
}
long long get_closest(int v) {
long long res = INF;
for (int c : centroids[v]) {
if (!distances[c].empty()) {
res = min(res, dist[level[c]][v] + *distances[c].begin());
}
}
return res;
}
void Init(int n, int a[], int b[], int d[]) {
for (int i = 0; i < n - 1; ++i) {
int u = a[i];
int v = b[i];
g[u].emplace_back(v, d[i]);
g[v].emplace_back(u, d[i]);
}
dfs_build();
}
long long Query(int n, int x[], int m, int y[]) {
for (int i = 0; i < n; ++i) {
add_vertex(x[i]);
}
long long res = INF;
for (int i = 0; i < m; ++i) {
res = min(res, get_closest(y[i]));
}
for (int i = 0; i < n; ++i) {
remove_vertex(x[i]);
}
return res;
}
