#include "factories.h"
#include <bits/stdc++.h>
#define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
using namespace std;
const long long INF = 1e16;
const int N = 5e5 + 5;
int n, q;
vector<pair<int, int>> g[N];
vector<pair<int, long long>> fa[N];
long long bst[N];
bool del[N];
int sz[N];
void get_sz(int u, int p) {
sz[u] = 1;
for(auto it : g[u]) if(it.first != p && !del[it.first]) {
get_sz(it.first, u);
sz[u] += sz[it.first];
}
}
int get_cen(int u, int p, int tt) {
for(auto it : g[u]) if(it.first != p && !del[it.first]) {
if(sz[it.first] * 2 > n) return get_cen(it.first, u, tt);
}
return u;
}
void dfs(int u, int p, int cen, long long d) {
fa[u].emplace_back(cen, d);
for(auto it : g[u]) if(!del[it.first] && it.first != p) {
dfs(it.first, u, cen, d + it.second);
}
}
void centroid(int u) {
get_sz(u, -1);
int cen = get_cen(u, -1, sz[u]);
del[cen] = true;
for(auto it : g[cen]) if(!del[it.first]) {
dfs(it.first, cen, cen, it.second);
}
for(auto it : g[cen]) if(!del[it.first]) centroid(it.first);
}
void Init(int _n, int A[], int B[], int D[]) {
memset(bst, 0x3f, sizeof bst);
n = _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]);
}
centroid(0);
// for(int i = 0; i < n; ++i) {
// for(auto [j, w] : fa[i]) cout << i << ' ' << j << ' ' << w << '\n';
// }
}
void upd(int u) {
bst[u] = 0;
for(auto it : fa[u]) bst[it.first] = min(bst[it.first], it.second);
}
long long get(int u) {
long long res = bst[u];
for(auto it : fa[u]) res = min(res, bst[it.first] + it.second);
return res;
}
void unupd(int u) {
bst[u] = INF;
for(auto it : fa[u]) bst[it.first] = INF;
}
long long Query(int S, int X[], int T, int Y[]) {
for(int i = 0; i < S; ++i) upd(X[i]);
long long res = INF;
for(int i = 0; i < T; ++i) res = min(res, get(Y[i]));
for(int i = 0; i < S; ++i) unupd(X[i]);
return res;
}
//int main() {
// ios_base::sync_with_stdio(false);
// cin.tie(0), cout.tie(0);
//
// file("A") else file("task");
// int _n, _q;
// cin >> _n >> _q;
// int A[_n], B[_n], D[_n];
// 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 X[S], Y[T];
// for(int i = 0; i < S; ++i) cin >> X[i];
// for(int i = 0; i < T; ++i) cin >> Y[i];
// cout << Query(S, X, T, Y) << '\n';
// }
// return 0;
//}
//
