#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long i64;
const int MAX_N = 500000 + 5;
const i64 INF = 1e18;
vector<pair<int, int>> g[MAX_N];
vector<pair<int, i64>> par[MAX_N];
int sub[MAX_N], del[MAX_N];
i64 best_way[MAX_N];
int calc_subtree(int node, int p) {
sub[node] = 1;
for (auto to : g[node]) {
if (to.first != p && !del[to.first]) {
sub[node] += calc_subtree(to.first, node);
}
}
return sub[node];
}
int calc_centroid(int node, int p, const int tam) {
for (auto to : g[node]) {
if (!del[to.first] && to.first != p && sub[to.first] > tam / 2) {
return calc_centroid(to.first, node, tam);
}
}
return node;
}
void solve(int node, int p, const int centroid, i64 w) {
par[node].emplace_back(centroid, w);
for (auto to : g[node]) {
if (!del[to.first] && to.first != p) {
solve(to.first, node, centroid, w + to.second);
}
}
}
void decompose(int node) {
const int centroid = calc_centroid(node, -1, calc_subtree(node, -1));
del[centroid] = 1;
for (auto to : g[centroid]) {
if (!del[to.first]) {
solve(to.first, -1, centroid, to.second);
decompose(to.first);
}
}
}
void Init(int N, int A[], int B[], int D[]) {
for (int i = 0; i < N - 1; i++) {
const int st = A[i];
const int et = B[i];
const int w = D[i];
g[st].emplace_back(et, w);
g[et].emplace_back(st, w);
}
decompose(0);
for (int i = 0; i < MAX_N; i++) {
best_way[i] = INF;
}
}
i64 Query(int S, int X[], int T, int Y[]) {
i64 mn = INF;
for (int i = 0; i < S; i++) {
best_way[X[i]] = 0;
for (auto to : par[X[i]]) {
best_way[to.first] = min(best_way[to.first], to.second);
}
}
for (int i = 0; i < T; i++) {
mn = min(mn, best_way[Y[i]]);
for (auto to : par[Y[i]]) {
mn = min(mn, best_way[to.first] + to.second);
}
}
for (int i = 0; i < S; i++) {
best_way[X[i]] = INF;
for (auto to : par[X[i]]) {
best_way[to.first] = INF;
}
}
return mn;
}
