#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<pair<int, int>>> g;
vector<int> sub;
vector<bool> alive;
vector<vector<pair<int, long long>>> ancs;
vector<long long> mn;
const long long inf = (long long) 1e18;
int dfs(int v, int pr) {
sub[v] = 1;
for (auto [u, w] : g[v]) {
if (u != pr && alive[u]) {
sub[v] += dfs(u, v);
}
}
return sub[v];
}
int find(int v, int pr, int sz) {
for (auto [u, w] : g[v]) {
if (u != pr && alive[u] && 2 * sub[u] > sz) {
return find(u, v, sz);
}
}
return v;
}
void distance(int v, int pr, int centroid, long long cur) {
for (auto [u, w] : g[v]) {
if (u != pr && alive[u]) {
distance(u, v, centroid, cur + w);
}
}
ancs[v].push_back(make_pair(centroid, cur));
}
void build(int v) {
int centroid = find(v, -1, dfs(v, -1));
for (auto [u, w] : g[centroid]) {
if (alive[u]) {
distance(u, centroid, centroid, w);
}
}
alive[centroid] = false;
for (auto [u, w] : g[centroid]) {
if (alive[u]) {
build(u);
}
}
}
vector<int> modified;
void paint(int v) {
for (auto [anc, d] : ancs[v]) {
mn[anc] = min(mn[anc], d);
modified.push_back(anc);
}
mn[v] = 0;
modified.push_back(v);
}
long long query(int v) {
long long ans = mn[v];
for (auto [anc, d] : ancs[v]) {
ans = min(ans, mn[anc] + d);
}
return ans;
}
void reset() {
for (int v : modified) {
mn[v] = inf;
}
modified.clear();
}
void Init(int n, int a[], int b[], int d[]) {
g.resize(n);
for (int i = 0; i < n - 1; i++) {
g[a[i]].emplace_back(b[i], d[i]);
g[b[i]].emplace_back(a[i], d[i]);
}
sub.resize(n);
alive.assign(n, true);
ancs.resize(n);
build(0);
mn.assign(n, inf);
}
long long Query(int s, int x[], int t, int y[]) {
for (int i = 0; i < s; i++) {
paint(x[i]);
}
long long ans = inf;
for (int i = 0; i < t; i++) {
ans = min(ans, query(y[i]));
}
reset();
return ans;
}
