#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
typedef long long ll;
typedef pair<int, ll> pii;
#define pb push_back
#define all(x) x.begin(), x.end()
// #define int ll
#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const ll inf = 1e18 + 10;
const int maxn = 1e6 + 10;
ll dist[maxn], sub[maxn];
vector<pii> G[maxn], cent[maxn];
bool dead[maxn];
int dfs_sz(int v, int p) {
sub[v] = 1;
for (auto [u, w] : G[v]) {
if (u == p || dead[u]) continue;
sub[v] += dfs_sz(u, v);
}
return sub[v];
}
int centroid(int v, int p, int sz) {
for (auto [u, w] : G[v]) {
if (u == p || dead[u]) continue;
if (sz < sub[u] * 2)
return centroid(u, v, sz);
}
return v;
}
void add(int v, int p, int tag, int d = 0) {
cent[v].pb({tag, d});
for (auto [u, w] : G[v]) {
if (u == p || dead[u]) continue;
add(u, v, tag, d + w);
}
}
void decomp(int v) {
int cen = centroid(v, -1, dfs_sz(v, -1));
add(cen, 0, cen);
dead[cen] = 1;
for (auto [u, w] : G[v]) {
if (dead[u]) continue;
decomp(u);
}
}
void Init(int N, int A[], int B[], int D[]) {
for (int i = 0; i < N - 1; i++) {
G[A[i]].pb({B[i], D[i]});
G[B[i]].pb({A[i], D[i]});
}
decomp(0);
}
ll Query(int S, int X[], int T, int Y[]) {
for (int i = 0; i < S; i++) {
for (auto [u, d] : cent[X[i]]) {
dist[u] = inf;
}
}
for (int i = 0; i < T; i++) {
for (auto [u, d] : cent[Y[i]]) {
dist[u] = min(dist[u], d);
}
}
ll ans = inf;
for (int i = 0; i < S; i++) {
for (auto [u, d] : cent[X[i]]) {
ans = min(ans, d + dist[u]);
}
}
return ans;
}
// int main() {
// int n, q;
// cin >> n >> q;
// int a[n + 1], b[n + 1], d[n + 1];
// for (int i = 0; i < n - 1; i++) {
// cin >> a[i] >> b[i] >> d[i];
// }
// Init(n, a, b, d);
// while (q--) {
// int s, t;
// cin >> s >> t;
// int S[s + 1], T[t + 1];
// for (int i = 0; i < s; i++)
// cin >> S[i];
// for (int i = 0; i < t; i++)
// cin >> T[i];
// cout << Query(s, S, t, T) << '\n';
// }
// }
