#include "factories.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cctype>
#include <string>
#include <queue>
#include <unordered_set>
#include <deque>
#include <numeric>
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimization("Ofast,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
typedef long long ll;
const ll INF = 1e15;
vector<vector<pair<int, ll>>> gr;
vector<int> sz;
vector<bool> blocked;
vector<vector<pair<int, ll>>> anc;
vector<ll> mindist;
vector<int> last;
int timer = 0;
int dfs_size(int v, int p = -1) {
sz[v] = 1;
for (auto& [u, w] : gr[v]) {
if (u != p && !blocked[u]) {
sz[v] += dfs_size(u, v);
}
}
return sz[v];
}
int find_centroid(int v, int total_size, int p = -1) {
for (auto& [u, w] : gr[v]) {
if (u != p && !blocked[u]) {
if (sz[u] * 2 >= total_size) {
return find_centroid(u, total_size, v);
}
}
}
return v;
}
void calc_dist(int v, int centr, ll d, int p = -1) {
anc[v].push_back({ centr, d });
for (auto& [u, w] : gr[v]) {
if (u != p && !blocked[u]) {
calc_dist(u, centr, d + w, v);
}
}
}
void build_decomposition(int v) {
int centr = find_centroid(v, dfs_size(v));
blocked[centr] = true;
anc[centr].push_back({ centr, 0 });
for (auto& [u, w] : gr[centr]) {
if (!blocked[u]) {
calc_dist(u, centr, w);
}
}
for (auto& [u, w] : gr[centr]) {
if (!blocked[u]) {
build_decomposition(u);
}
}
}
void Init(int N, int A[], int B[], int D[]) {
ios_base::sync_with_stdio(false);
cin.tie(0);
gr.resize(N);
for (int i = 0; i < N - 1; ++i) {
int u = A[i], v = B[i], d = D[i];
gr[u].push_back({ v, d });
gr[v].push_back({ u, d });
}
sz.resize(N);
blocked.resize(N);
anc.resize(N);
mindist.resize(N, INF);
last.resize(N, -1);
build_decomposition(0);
}
void paint(int v, int timer) {
for (auto& [p, d] : anc[v]) {
if (last[p] != timer) {
mindist[p] = d;
} else {
mindist[p] = min(mindist[p], d);
}
last[p] = timer;
}
}
ll get_mindist(int v, int timer) {
ll ans = INF;
for (auto& [p, d] : anc[v]) {
if (last[p] == timer) {
ans = min(ans, d + mindist[p]);
}
}
return ans;
}
ll Query(int S, int X[], int T, int Y[]) {
for (int i = 0; i < S; ++i) {
paint(X[i], timer);
}
ll ans = INF;
for (int i = 0; i < T; ++i) {
ans = min(ans, get_mindist(Y[i], timer));
}
timer++;
return ans;
}
