#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 5e5 + 5, INF = 1e18;
int n;
vector<pair<int,int>> adj[maxn];
vector<pair<int,int>> vec[maxn];
int cent = -1, sz;
int dfs(int u, int p) {
int usz = 1;
bool can = true;
for (auto [v, w]:adj[u]) if (v != p) {
int cur = dfs(v, u);
if (cur > sz / 2) can = false;
usz += cur;
}
// cout << u << " " << usz << " " << can << endl;
if (can && sz - usz <= sz / 2) cent = u;
return usz;
}
void dfs2(int u, int dist, int p) {
vec[u].push_back({cent, dist});
for (auto [v, w]:adj[u]) if (v != p) dfs2(v, dist + w, u);
}
vector<int> nodes;
void dfs3(int u, int p) {
nodes.push_back(u);
// cout << "dfs3 " << u << endl;
for (auto [v, w]:adj[u]) if (v != p) {
// cout << u << " " << v << endl;
dfs3(v, u);
}
}
void decomp(int u) {
sz = nodes.size(), cent = u;
dfs(u, -1);
// cout << u << " " << sz << " " << cent << endl;
// for (int i:nodes) cout << i << " "; cout << endl;
int curcent = cent;
dfs2(cent, 0, -1);
for (auto [v, w]:adj[curcent]) {
adj[v].erase(find(adj[v].begin(), adj[v].end(), make_pair(curcent, w)));
nodes.clear();
// cout << u << " " << v << endl;
dfs3(v, -1);
decomp(v);
}
}
int mn[maxn];
void Init(int32_t N, int32_t A[], int32_t B[], int32_t D[]) {
n = N;
for (int i=0;i<n-1;i++) {
adj[A[i]].push_back({B[i], D[i]});
adj[B[i]].push_back({A[i], D[i]});
}
for (int i=0;i<n;i++) nodes.push_back(i);
decomp(0);
// cout << "test\n";
for (int i=0;i<n;i++) mn[i] = INF;
}
int Query(int32_t S, int32_t X[], int32_t T, int32_t Y[]) {
for (int i=0;i<S;i++) {
for (auto [c, val]:vec[X[i]]) mn[c] = min(val, mn[c]);
}
int ans = INF;
for (int i=0;i<T;i++) {
for (auto [c, val]:vec[Y[i]]) ans = min(val + mn[c], ans);
}
for (int i=0;i<S;i++) {
for (auto [c, val]:vec[X[i]]) mn[c] = INF;
}
return ans;
}
