#include <bits/stdc++.h>
#include "factories.h"
#define pb push_back
#define LINF 0x3f3f3f3f3f3f3f3f
#define endl '\n'
#define ll long long
#define f first
#define s second
using namespace std;
typedef pair<ll, ll> pii;
const int MAXN = 5e5 + 5;
ll sub_size[MAXN], visited[MAXN], best[MAXN];
vector<pii> adj[MAXN], dis[MAXN];
// Find subtree size.
int subSize(int cur, int par) {
sub_size[cur] = 1;
for (pii next : adj[cur])
if (next.f != par && !visited[next.f])
sub_size[cur] += subSize(next.f, cur);
return sub_size[cur];
}
// Return the centroid.
int findCentroid(int cur, int par, int N) {
for (pii next : adj[cur]) {
if (next.f != par && !visited[next.f] && sub_size[next.f] > N / 2) {
return findCentroid(next.f, cur, N);
}
}
return cur;
}
void getDis(int cur, int par, int c, ll dist) {
dis[cur].pb({ c, dist });
for (pii next : adj[cur]) {
if (next.f != par && !visited[next.f]) {
getDis(next.f, cur, c, dist + next.s);
}
}
}
void build(int cur) {
int centroid = findCentroid(cur, -1, subSize(cur, -1));
getDis(centroid, -1, centroid, 0);
visited[centroid] = 1;
for (pii next : adj[centroid]) {
if (!visited[next.f]) {
build(next.f);
}
}
}
// Initialize function
void Init(int n, int a[], int b[], int c[]) {
// Read edges
for (int i = 0; i < n - 1; i++) {
adj[a[i]].pb({ b[i], c[i] });
adj[b[i]].pb({ a[i], c[i] });
}
build(0);
fill(best, best + MAXN, LINF);
}
// Process queries
ll Query(int len1, int x[], int len2, int y[]) {
ll ans = LINF;
for (int u = 0; u < len1; u++) {
for (pii i : dis[x[u]]) {
best[i.f] = min(best[i.f], i.s);
}
}
for (int u = 0; u < len2; u++) {
for (pii i : dis[y[u]]) {
ans = min(ans, best[i.f] + i.s);
}
}
for (int u = 0; u < len1; u++) {
for (pii i : dis[x[u]]) {
best[i.f] = LINF;
}
}
return ans;
}
