#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
const int mn = 5e5 + 5;
int centroid[mn][19], sz[mn];
long long depth[mn][19];
bool removed[mn];
vector<pair<int,int>> adj[mn], container[mn];
int szDfs (int u, int p) {
sz[u] = 1;
for (auto [v, w] : adj[u])
if (!removed[v] && v != p) sz[u] += szDfs(v, u);
return sz[u];
}
int findCentroid (int u, int p, int sztr) {
for (auto [v, w] : adj[u])
if (!removed[v] && v != p && sz[v] > sztr / 2) return findCentroid(v, u, sztr);
return u;
}
void dfsTree (int u, int p, int root, int level, long long wd) {
centroid[u][level] = root, depth[u][level] = wd;
for (auto [v, w] : adj[u])
if (!removed[v] && v != p) dfsTree(v, u, root, level, wd + w);
}
void centroidDecomposition (int u, int level = 0) {
szDfs(u, u);
int root = findCentroid(u, u, sz[u]);
// cout << "centroid decomposition " << u << " " << root << " " << level << endl;
dfsTree(root, root, root, level, 0);
removed[root] = true;
for (auto [v, w] : adj[root])
if (!removed[v]) centroidDecomposition(v, level + 1);
}
long long centroidQuery (int root, const vector<pair<int,int>> &query, int level = 0) {
for (auto [u, type] : query) {
int node = (centroid[u][level + 1] ? centroid[u][level + 1] : root);
container[node].emplace_back(u, type);
}
long long bestA = LLONG_MAX, bestB = LLONG_MAX, ans = LLONG_MAX;
for (auto [u, type] : query) {
int c = (centroid[u][level + 1] ? centroid[u][level + 1] : root);
for (auto [node, type] : container[c]) {
if (type && bestA != LLONG_MAX) ans = min(ans, bestA + depth[node][level]);
if (!type && bestB != LLONG_MAX) ans = min(ans, bestB + depth[node][level]);
}
for (auto [node, type] : container[c]) {
long long &target = (type ? bestB : bestA);
target = min(target, depth[node][level]);
}
if (centroid[u][level + 1] && container[c].size())
ans = min(ans, centroidQuery(c, container[c], level + 1));
container[c].clear();
}
return ans;
}
void Init (int N, int A[], int B[], int D[]) {
for (int i = 0; i < N - 1; i++) {
A[i]++, B[i]++;
adj[A[i]].emplace_back(B[i], D[i]);
adj[B[i]].emplace_back(A[i], D[i]);
}
centroidDecomposition(1);
}
long long Query (int S, int X[], int T, int Y[]) {
vector<pair<int,int>> query;
query.reserve(S + T);
for (int i = 0; i < S; i++)
query.emplace_back(X[i] + 1, 0);
for (int i = 0; i < T; i++)
query.emplace_back(Y[i] + 1, 1);
return centroidQuery(centroid[1][0], query);
}
