#include "factories.h"
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;
typedef long long llong;
typedef pair<llong, llong> pll;
struct _edge {
int x, d;
_edge(int x, int d) : x(x), d(d) {}
};
int n;
vector<_edge> edge[500001];
int dep[500001];
llong dist[500001];
int st[500001];
int ed[500001];
int par[500001][20];
void dfs(int x, int p) {
static int ord = 0;
st[x] = ++ord;
par[x][0] = p;
for (int i = 1; i < 20; ++i) {
par[x][i] = par[par[x][i - 1]][i - 1];
}
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);
}
ed[x] = ord;
}
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 (dep[x] < dep[y]) swap(x, y);
for (int i = 20; i--; ) {
if ((dep[x] - dep[y]) >> i) x = par[x][i];
}
if (x == y) return x;
for (int i = 20; i--; ) {
if (par[x][i] != par[y][i]) {
x = par[x][i];
y = par[y][i];
}
}
return par[x][0];
}
const llong inf = 1e16;
int in[500001];
int m, idx;
vector<int> qs;
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[]) {
qs.clear();
for (int i = 0; i < S; ++i) {
qs.push_back(++X[i]);
}
for (int i = 0; i < T; ++i) {
qs.push_back(++Y[i]);
}
sort(qs.begin(), qs.end(), [&](int i, int j) { return st[i] < st[j]; });
m = qs.size();
for (int i = 1; i < m; ++i) {
qs.push_back(lca(qs[i - 1], qs[i]));
}
sort(qs.begin(), qs.end(), [&](int i, int j) { return st[i] < st[j]; });
qs.erase(unique(qs.begin(), qs.end()), qs.end());
m = qs.size();
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;
}
