#include "factories.h"
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;
typedef long long llong;
typedef pair<int, int> pii;
typedef pair<llong, llong> pll;
struct _edge {
int x, d;
_edge(int x, int d) : x(x), d(d) {}
};
int n, k;
vector<_edge> edge[500001];
int dep[500001];
llong dist[500001];
int st[500001];
int ed[500001];
int ord[1000000];
pii seg[1000000][21];
int pw[1000001];
int sz;
void dfs(int x, int p) {
ord[st[x] = k++] = x;
for (_edge i : edge[x]) {
if (i.x == p) continue;
dep[i.x] = dep[x] + 1;
dist[i.x] = dist[x] + i.d;
dfs(i.x, x);
ord[k++] = x;
}
ed[x] = k;
}
void init() {
for (int i = 1, j = 0; i <= 1000000; ++i) {
if ((1 << (j + 1)) < i) ++j;
pw[i] = j;
}
for (int i = 0; i < k; ++i) {
seg[i][0] = pii(dep[ord[i]], ord[i]);
}
for (int i = 1; i < 21; ++i) {
for (int j = 0; j < k; ++j) {
seg[j][i] = seg[j][i - 1];
if (j + (1 << (i - 1)) < k) {
seg[j][i] = min(seg[j][i], seg[j + (1 << (i - 1))][i - 1]);
}
}
}
}
void Init(int N, int A[], int B[], int D[]) {
n = N;
for (int i = 0; i < n - 1; ++i) {
++A[i]; ++B[i];
edge[A[i]].emplace_back(B[i], D[i]);
edge[B[i]].emplace_back(A[i], D[i]);
}
dfs(1, 0);
}
int lca(int x, int y) {
if (x == y) return x;
x = st[x]; y = st[y];
if (x > y) swap(x, y);
int t = pw[y - x + 1];
return min(seg[x][t], seg[y - (1 << t) + 1][t]).second;
}
const llong inf = 1e16;
int in[500001];
int m, idx;
int qs[1000000];
llong ans;
pll dfs2() {
llong d = dist[qs[idx]];
llong mx = d + ((in[qs[idx]] == 1) ? 0 : inf);
llong my = d + ((in[qs[idx]] == 2) ? 0 : inf);
int e = ed[qs[idx++]];
while (idx < m) {
if (e < st[qs[idx]]) break;
llong rx, ry;
tie(rx, ry) = dfs2();
ans = min({ ans, mx + ry - d - d, my + rx - d - d });
mx = min(mx, rx);
my = min(my, ry);
}
return pll(mx, my);
}
llong Query(int S, int X[], int T, int Y[]) {
m = 0;
for (int i = 0; i < S; ++i) {
qs[m++] = ++X[i];
}
for (int i = 0; i < T; ++i) {
qs[m++] = ++Y[i];
}
sort(qs, qs + m, [&](int i, int j) { return st[i] < st[j]; });
for (int i = 0; i + 1 < m; ++i) {
qs[m + i] = lca(qs[i], qs[i + 1]);
}
m = (m << 1) - 1;
sort(qs, qs + m, [&](int i, int j) { return st[i] < st[j]; });
m = unique(qs, qs + m) - qs;
for (int i = 0; i < m; ++i) in[qs[i]] = 0;
for (int i = 0; i < S; ++i) in[X[i]] = 1;
for (int i = 0; i < T; ++i) in[Y[i]] = 2;
idx = 0;
ans = inf;
dfs2();
return ans;
}
