#include "factories.h"
#include <bits/stdc++.h>
// #include <ext/rope>
// #include <ext/pb_ds/assoc_container.hpp>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
// #define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>
#define ll long long
#define ull unsigned long long
#define ld long double
#define pb push_back
#define bit(mask, i) ((mask >> i) & 1)
#define el '\n'
#define F first
#define S second
template <class X, class Y> bool maximize(X &x, const Y &y) { return (x < y ? x = y, 1 : 0); }
template <class X, class Y> bool minimize(X &x, const Y &y) { return (x > y ? x = y, 1 : 0); }
const ll INF = 1e9;
const ll LINF = 1e18;
const ll MOD = 1e9 + 7;
const ll MULTI = 0;
const ld eps = 1e-9;
const ll dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0}; // R D L U
const ll ddx[4] = {-1, 1, 1, -1}, ddy[4] = {1, 1, -1, -1}; // UR DR DL UL
const char cx[4] = {'R', 'D', 'L', 'U'};
const ll base = 31;
const ll nMOD = 2;
const ll mods[] = {(ll)1e9 + 10777, (ll)1e9 + 19777, (ll)1e9 + 3, (ll)1e9 + 3777};
const ll N = 5e5 + 5;
ll n, ti[N], to[N], et[N], timeDfs;
ll d[N], res;
vector<pair<ll, ll>> adj[N], aux_adj[N];
bool A[N], B[N];
void pre_dfs(ll u, ll p) {
ti[u] = ++timeDfs;
et[timeDfs] = u;
for (auto v: adj[u])
if (v.F != p)
pre_dfs(v.F, u);
to[u] = timeDfs;
}
bool is_ancestor(ll u, ll v) {
return ti[u] <= ti[v] && ti[v] <= to[u];
}
namespace LCA {
const ll LOG = 19;
ll ti[N], et[2 * N], lg2[2 * N], timeDfs = 1, h[N];
ll d[N];
pair<ll, ll> st[LOG + 1][2 * N];
void dfs(ll u, ll p) {
ti[u] = timeDfs;
et[timeDfs++] = u;
for (auto g: adj[u]) {
ll v = g.F, w = g.S;
if (v != p) {
h[v] = h[u] + 1;
d[v] = d[u] + w;
dfs(v, u);
et[timeDfs++] = u;
}
}
}
void preprocess() {
lg2[1] = 0;
for (ll i = 2; i <= 2 * n; ++i) lg2[i] = lg2[i / 2] + 1;
for (ll i = 1; i <= 2 * n; ++i) st[0][i] = make_pair(h[et[i]], et[i]);
for (ll j = 1; j <= LOG; ++j)
for (ll i = 1; i + (1 << j) - 1 <= 2 * n; ++i)
st[j][i] = min(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
}
pair<ll, ll> query(ll l, ll r) {
ll k = lg2[r - l + 1];
return min(st[k][l], st[k][r - (1 << k) + 1]);
}
ll lca(ll u, ll v) {
if (ti[u] > ti[v]) swap(u, v);
return query(ti[u], ti[v]).S;
}
ll dist(ll u, ll v) {
return d[u] + d[v] - 2 * d[lca(u, v)];
}
void build() {
dfs(1, 0);
preprocess();
}
}
struct IT {
ll st[4 * N], lazy[4 * N];
void build(ll id, ll l, ll r) {
st[id] = LINF;
if (l == r) return;
ll mid = (l + r) >> 1;
build(id << 1, l, mid);
build(id << 1 | 1, mid + 1, r);
}
void push(ll id, ll l, ll r) {
ll &t = lazy[id];
if (t == 0) return;
st[id << 1] += t;
lazy[id << 1] += t;
st[id << 1 | 1] += t;
lazy[id << 1 | 1] += t;
t = 0;
}
void updateMass(ll id, ll l, ll r, ll u, ll x) {
if (l == r) return st[id] = x, void();
ll mid = (l + r) >> 1; push(id, l, r);
if (u <= mid) updateMass(id << 1, l, mid, u, x);
else updateMass(id << 1 | 1, mid + 1, r, u, x);
st[id] = min(st[id << 1], st[id << 1 | 1]);
}
void update(ll id, ll l, ll r, ll u, ll v, ll x) {
if (u > v) return;
if (l == u && r == v) return st[id] += x, lazy[id] += x, void();
ll mid = (l + r) >> 1; push(id, l, r);
if (v <= mid) update(id << 1, l, mid, u, v, x);
else if (u > mid) update(id << 1 | 1, mid + 1, r, u, v, x);
else {
update(id << 1, l, mid, u, mid, x);
update(id << 1 | 1, mid + 1, r, mid + 1, v, x);
}
st[id] = min(st[id << 1], st[id << 1 | 1]);
}
} IT;
void Init(int N, int A[], int B[], int D[]) {
n = N;
for (ll i = 0; i <= n - 2; ++i) {
A[i]++; B[i]++;
adj[A[i]].push_back(make_pair(B[i], D[i]));
adj[B[i]].push_back(make_pair(A[i], D[i]));
}
pre_dfs(1, 0);
LCA::build();
IT.build(1, 1, n);
}
ll build_auxiliary_tree(vector<ll> &vers) {
ll sz = (ll) vers.size();
sort(vers.begin(), vers.end(), [&](ll A, ll B){
return ti[A] < ti[B];
});
for (ll i = 0; i < sz - 1; ++i) {
ll lca = LCA::lca(vers[i], vers[i + 1]);
vers.push_back(lca);
}
sort(vers.begin(), vers.end(), [&](ll A, ll B){
return ti[A] < ti[B];
});
vers.resize(unique(vers.begin(), vers.end()) - vers.begin());
vector<ll> stack;
ll aux_root = vers[0];
stack.push_back(aux_root);
for (ll i = 1; i < (ll) vers.size(); ++i) {
ll u = vers[i];
while (!stack.empty() && !is_ancestor(stack.back(), u))
stack.pop_back();
assert(!stack.empty());
ll last = stack.back();
aux_adj[last].push_back(make_pair(u, LCA::dist(last, u)));
stack.push_back(u);
}
return aux_root;
}
void dfs1(ll u, ll p) {
for (auto g: aux_adj[u]) {
ll v = g.F, w = g.S;
if (v == p) continue;
d[v] = d[u] + w;
dfs1(v, u);
}
}
void dfs2(ll u, ll p) {
for (auto g: aux_adj[u]) {
ll v = g.F, w = g.S;
if (v == p) continue;
IT.update(1, 1, n, ti[v], to[v], -w);
IT.update(1, 1, n, 1, ti[v] - 1, w);
IT.update(1, 1, n, to[v] + 1, n, w);
if (B[v]) minimize(res, IT.st[1]);
dfs2(v, u);
IT.update(1, 1, n, ti[v], to[v], w);
IT.update(1, 1, n, 1, ti[v] - 1, -w);
IT.update(1, 1, n, to[v] + 1, n, -w);
}
}
ll Query(int S, int X[], int T, int Y[]) {
vector<ll> vers;
for (ll i = 0; i < S; ++i) {
A[++X[i]] = 1;
vers.push_back(X[i]);
}
for (ll i = 0; i < T; ++i) {
B[++Y[i]] = 1;
vers.push_back(Y[i]);
}
ll root = build_auxiliary_tree(vers);
dfs1(root, 0);
for (ll i = 0; i < S; ++i) IT.updateMass(1, 1, n, ti[X[i]], d[X[i]]);
res = (B[root] ? IT.st[1] : LINF);
dfs2(root, 0);
for (auto x: vers) aux_adj[x].clear(), d[x] = 0;
for (ll i = 0; i < S; ++i) {
IT.updateMass(1, 1, n, ti[X[i]], LINF);
A[X[i]] = 0;
}
for (ll i = 0; i < T; ++i) B[Y[i]] = 0;
return res;
}
