#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using ibi = tuple<int, bool, int>;
const int N = 500'005, lg = 20;
ll dist[lg][N], ans[N];
int pa[lg][N], sz[N];
bool rm[N];
vector<pii> adj[N];
queue<int> q;
int get_sz(int u, int p) {
sz[u] = 1;
for (auto [v, w]: adj[u]) if (v != p && !rm[v]) sz[u] += get_sz(v, u);
return sz[u];
}
int get_ct(int u, int p, int n) {
for (auto [v, w]: adj[u]) if (v != p && !rm[v] && sz[v] > n/2) return get_ct(v, u, n);
return u;
}
void get_dist(int u, int p, int de, int ct) {
for (auto [v, w]: adj[u]) if (v != p && !rm[v]) {
dist[de][v] = dist[de][u] + w;
pa[de][v] = ct;
get_dist(v, u, de, ct);
}
}
void decompose(int u, int de, int p) {
int n = get_sz(u, -1);
int ct = get_ct(u, -1, n);
pa[de][ct] = ct;
get_dist(ct, -1, de, ct);
rm[ct] = 1;
for (auto [v, w]: adj[ct]) if (!rm[v]) decompose(v, de + 1, ct);
}
void Init(int N, int A[], int B[], int D[]) {
for (int i = 0; i < N-1; i++) {
adj[A[i]].emplace_back(B[i], D[i]);
adj[B[i]].emplace_back(A[i], D[i]);
}
memset(pa, -1, sizeof pa);
decompose(0, 0, -1);
memset(ans, 0x3f, sizeof ans);
}
long long Query(int S, int X[], int T, int Y[]) {
ll ret = LLONG_MAX;
for (int i = 0; i < lg; i++) for (int j = 0; j < S; j++) if (pa[i][X[j]] != -1) {
ans[pa[i][X[j]]] = min(ans[pa[i][X[j]]], dist[i][X[j]]);
}
for (int i = 0; i < lg; i++) for (int j = 0; j < T; j++) if (pa[i][Y[j]] != -1) {
ret = min(ret, ans[pa[i][Y[j]]] + dist[i][Y[j]]);
}
for (int i = 0; i < lg; i++) for (int j = 0; j < S; j++) if (pa[i][X[j]] != -1) {
ans[pa[i][X[j]]] = 0x3f3f3f3f3f3f3f3f;
}
return ret;
}
