#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define ll long long
#define bit(mask, i) ((mask >> i) & 1)
#define pb push_back
const int N = 5e5 + 10;
const int LG = 20;
const ll inf = 1e18;
vector<pair<int, ll>> a[N], vtree[N];
int n, timer;
int tin[N], tout[N], tour[N], par[N], jump[N][LG], depth[N];
ll dist[N];
unordered_map<int, int> mp, color;
vector<int> type;
vector<ll> dp1, dp2;
bool cmp(int u, int v) {
return tin[u] < tin[v];
}
void dfs1(int u, int p) {
par[u] = p;
tin[u] = ++timer;
tour[timer] = u;
for (auto &[v, w] : a[u]) {
if (v == p) continue;
depth[v] = depth[u] + 1;
dist[v] = dist[u] + w;
dfs1(v, u);
}
tout[u] = timer;
}
void build_jump() {
for (int i = 0; i < n; ++i) {
jump[i][0] = par[i];
}
for (int j = 1; j < LG; ++j) {
for (int i = 0; i < n; ++i) {
if (jump[i][j - 1] != -1) {
jump[i][j] = jump[jump[i][j - 1]][j - 1];
}
}
}
}
int take(int u, int v) {
int delta = depth[u] - depth[v];
for (int i = 0; (1 << i) <= delta; ++i) {
if (bit(delta, i)) {
u = jump[u][i];
}
}
return u;
}
int lca(int u, int v) {
if (depth[u] != depth[v]) {
if (depth[u] < depth[v]) swap(u, v);
u = take(u, v);
}
if (u == v) return u;
for (int i = LG - 1; i >= 0; --i) {
if (jump[u][i] != jump[v][i]) {
u = jump[u][i];
v = jump[v][i];
}
}
return jump[u][0];
}
bool is_ancestor(int u, int v) {
return tin[u] <= tin[v] && tout[v] <= tout[u];
}
ll get(int u, int v) {
return dist[u] + dist[v] - 2 * dist[lca(u, v)];
}
vector<int> buildtree(vector<int> tree) {
sort(tree.begin(), tree.end(), cmp);
int sz = tree.size();
for (int i = 0; i < sz - 1; ++i) {
tree.pb(lca(tree[i], tree[i + 1]));
}
sort(tree.begin(), tree.end());
tree.erase(unique(tree.begin(), tree.end()), tree.end());
sort(tree.begin(), tree.end(), cmp);
stack<int> st;
st.push(tree[0]);
for (int i = 1; i < tree.size(); ++i) {
while (!is_ancestor(st.top(), tree[i])) st.pop();
vtree[st.top()].pb({tree[i], get(st.top(), tree[i])});
st.push(tree[i]);
}
return tree;
}
int change(int x) {
return mp[x];
}
void dfs2(int u, int p) {
int _u = change(u);
if (color[u] == 1) dp1[_u] = 0;
if (color[u] == 2) dp2[_u] = 0;
for (auto &[v, w] : vtree[u]) {
if (v == p) continue;
dfs2(v, u);
int _v = change(v);
dp1[_u] = min(dp1[_u], dp1[_v] + w);
dp2[_u] = min(dp2[_u], dp2[_v] + w);
}
}
// ============================
// Required functions for JOI:
// ============================
void Init(int N_, int A[], int B[], int D[]) {
n = N_;
for (int i = 0; i < n - 1; ++i) {
int u = A[i], v = B[i]; ll w = D[i];
a[u].pb({v, w});
a[v].pb({u, w});
}
timer = 0;
dfs1(0, -1);
build_jump();
}
long long Query(int S, int X[], int T, int Y[]) {
vector<int> tree;
for (int i = 0; i < S; ++i) {
tree.pb(X[i]);
color[X[i]] = 1;
}
for (int i = 0; i < T; ++i) {
tree.pb(Y[i]);
color[Y[i]] = 2;
}
tree = buildtree(tree);
int root = tree[0], sz = tree.size();
for (int i = 0; i < sz; ++i) {
type.pb(color[tree[i]]);
mp[tree[i]] = i;
}
dp1.assign(sz, inf), dp2.assign(sz, inf);
dfs2(root, -1);
ll res = inf;
for (int i = 0; i < sz; ++i) {
res = min(res, dp1[i] + dp2[i]);
}
// Clear memory
for (int i = 0; i < sz; ++i) {
vtree[tree[i]].clear();
}
color.clear(); mp.clear(); type.clear(); dp1.clear(); dp2.clear();
return res;
}
