#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
const int mn = 5e5 + 5;
vector<pair<int,int>> adj[mn], container[mn];
int centroid[mn][21], sz[mn];
long long depth[mn][21];
bool removed[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, tmp] : query) {
int c = (centroid[u][level + 1] ? centroid[u][level + 1] : root);
if (container[c].empty()) continue;
if (!centroid[u][level + 1] && container[c].front().second != container[c].back().second) ans = 0;
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]) {
if (type) bestB = min(bestB, depth[node][level]);
else bestA = min(bestA, depth[node][level]);
}
vector<pair<int,int>> holder = container[c];
container[c].clear();
if (centroid[u][level + 1])
ans = min(ans, centroidQuery(c, holder, level + 1));
}
return ans;
}
// void Init (int N, vector<int> A, vector<int> B, vector<int> D) {
void Init (int N, int A[], int B[], int D[]) {
for (int i = 0; i < N - 1; i++) {
adj[A[i] + 1].emplace_back(B[i] + 1, D[i]);
adj[B[i] + 1].emplace_back(A[i] + 1, D[i]);
}
centroidDecomposition(1);
}
// long long Query (int S, vector<int> X, int T, vector<int> Y) {
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);
}
