#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pii pair<ll, ll>
const int N = 500005;
const ll INF = 1e18;
vector<pii> adj[N];
int del[N], child[N];
ll high[N], dist[N], min_dist[N];
vector<pii> par[N];
void cnt_child(int u, int parent) {
child[u] = 1;
for (auto &v : adj[u]) {
if (v.first == parent || del[v.first]) continue;
cnt_child(v.first, u);
child[u] += child[v.first];
}
}
int get_centroid(int u, int parent, int total) {
for (auto &v : adj[u]) {
if (v.first == parent || del[v.first]) continue;
if (child[v.first] > total / 2)
return get_centroid(v.first, u, total);
}
return u;
}
void dfs(int u, int parent, int root) {
par[u].emplace_back(root, dist[u]);
for (auto &v : adj[u]) {
if (v.first == parent || del[v.first]) continue;
high[v.first] = high[u] + 1;
dist[v.first] = dist[u] + v.second;
dfs(v.first, u, root);
}
}
void build_centroid(int u) {
cnt_child(u, -1);
int c = get_centroid(u, -1, child[u]);
high[c] = dist[c] = 0;
dfs(c, -1, c);
del[c] = 1;
for (auto &v : adj[c]) {
if (!del[v.first])
build_centroid(v.first);
}
}
void Init(int n, int A[], int B[], int D[]) {
for (int i = 0; i < n - 1; i++) {
int u = A[i], v = B[i], w = D[i];
adj[u].emplace_back(v, w);
adj[v].emplace_back(u, w);
}
build_centroid(0);
for (int i = 0; i < n; i++) {
min_dist[i] = INF;
}
}
long long Query(int S, int X[], int T, int Y[]) {
vector<int> temp; // lưu lại các đỉnh được cập nhật để khôi phục sau
for (int i = 0; i < S; i++) {
int u = X[i];
for (auto &p : par[u]) {
min_dist[p.first] = min(min_dist[p.first], p.second);
temp.push_back(p.first);
}
}
ll res = INF;
for (int i = 0; i < T; i++) {
int u = Y[i];
for (auto &p : par[u]) {
res = min(res, p.second + min_dist[p.first]);
}
}
for (int x : temp) {
min_dist[x] = INF; // khôi phục lại
}
return res;
}
