#include "factories.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = (int)5e5 + 7;
int tiktak;
int tin[maxn], tout[maxn];
int lc[20][maxn];
ll h[maxn];
vector<pair<int, int>> gr[maxn];
int numlog[maxn + maxn], pos[maxn], deep[maxn];
vector <int> order;
struct sparse {
pair<int, int> table[20][maxn + maxn];
sparse() {}
void build() {
for (int i = 2; i <= order.size(); i++) {
numlog[i] = numlog[i / 2] + 1;
}
for (int i = 0; i <= numlog[order.size()]; i++) {
for (int j = 0; j < order.size(); j++) {
if (i == 0) {
table[i][j] = {deep[order[j]], order[j]};
} else {
table[i][j] = min(table[i - 1][j], table[i - 1][min(j + (1 << i - 1), (int)order.size() - 1)]);
}
}
}
}
int get(int l, int r) {
if (l > r) swap(l, r);
int lg = numlog[r - l + 1];
return min(table[lg][l], table[lg][r - (1 << lg) + 1]).second;
}
};
sparse tr;
void dfs(int v, int pr) {
pos[v] = order.size();
order.push_back(v);
for (auto id : gr[v]) {
int to = id.first;
int w = id.second;
if (to == pr) continue;
h[to] = h[v] + w;
deep[to] = deep[v] + 1;
dfs(to, v);
pos[v] = order.size();
order.push_back(v);
}
}
int lca(int a, int b) {
return tr.get(pos[a], pos[b]);
}
ll dist(int a, int b) {
return h[a] + h[b] - 2 * h[lca(a, b)];
}
void Init(int N, int A[], int B[], int D[]) {
for (int i = 0; i < N - 1; i++) {
gr[A[i]].push_back({B[i], D[i]});
gr[B[i]].push_back({A[i], D[i]});
}
dfs(0, 0);
tr.build();
}
ll dp1[maxn], dp2[maxn];
int col[maxn];
void dfs1(int v, int pr, ll &ans) {
dp1[v] = 1e18;
dp2[v] = 1e18;
if (col[v] == 1) dp1[v] = 0;
if (col[v] == 2) dp2[v] = 0;
for (pair<int, int> id : gr[v]) {
int to = id.first;
int w = id.second;
if (to == pr) continue;
dfs1(to, v, ans);
dp1[v] = min(dp1[v], dp1[to] + w);
dp2[v] = min(dp2[v], dp2[to] + w);
}
ans = min(ans, dp1[v] + dp2[v]);
}
long long Query(int S, int X[], int T, int Y[]) {
ll ans = 1e18;
if (S <= 10 && T <= 10) {
for (int i = 0; i < S; i++) {
for (int j = 0; j < T; j++) {
ans = min(ans, dist(X[i], Y[j]));
}
}
return ans;
}
for (int i = 0; i < S; i++) {
col[X[i]] = 1;
}
for (int i = 0; i < T; i++) {
col[Y[i]] = 2;
}
dfs1(1, 1, ans);
for (int i = 0; i < S; i++) {
col[X[i]] = 0;
}
for (int i = 0; i < T; i++) {
col[Y[i]] = 0;
}
return ans;
}
