#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll inf = 1e18;
vector<vector<array<ll, 2>>> adj;
vector<vector<int>> jmp;
vector<int> tin, tout;
vector<bool> sn, tn;
vector<ll> d, mxs, mxt, rs, rt;
bool cmp(int u, int v) {
return tin[u] < tin[v];
}
bool upper(int u, int v) {
return tin[v] >= tin[u] && tout[v] <= tout[u];
}
bool chmin(ll &a, const ll &b) {
return a > b ? a = b, true : false;
}
bool chmax(ll &a, const ll &b) {
return a < b ? a = b, true : false;
}
int lca(int u, int v) {
if(upper(u, v)) return u;
for(int i = 19; i >= 0; i--) {
if(!upper(jmp[u][i], v)) {
u = jmp[u][i];
}
}
return jmp[u][0];
}
void Init(int n, int a[], int b[], int D[]) {
adj.resize(n);
jmp.resize(n);
sn.resize(n);
tn.resize(n);
mxs.resize(n);
mxt.resize(n);
rs.resize(n);
rt.resize(n);
tin.resize(n);
tout.resize(n);
d.resize(n);
for(int i = 0; i < n; i++) {
jmp[i].resize(20);
}
for(int i = 0; i < n - 1; i++) {
adj[a[i]].push_back({b[i], D[i]});
adj[b[i]].push_back({a[i], D[i]});
}
int timer = 0;
auto dfs = [&](auto &&self, int v, int p) -> void {
jmp[v][0] = p;
for(int i = 1; i < 20; i++) {
jmp[v][i] = jmp[ jmp[v][i - 1] ][i - 1];
}
tin[v] = ++timer;
for(auto [to, c] : adj[v]) {
if(to == p) continue;
d[to] = d[v] + c;
self(self, to, v);
}
tout[v] = timer;
};
dfs(dfs, 0, 0);
for(int i = 0; i < n; i++) {
adj[i].clear();
}
}
long long Query(int s, int x[], int t, int y[]) {
vector<int> ver;
for(int i = 0; i < s; i++) {
ver.push_back(x[i]);
}
for(int i = 0; i < t; i++) {
ver.push_back(y[i]);
}
sort(ver.begin(), ver.end(), cmp);
for(int i = 0; i + 1 < s + t; i++) {
ver.push_back( lca(ver[i], ver[i + 1]) );
}
sort(ver.begin(), ver.end(), cmp);
ver.erase(unique(ver.begin(), ver.end()), ver.end());
for(auto &v : ver) {
adj[v].clear();
sn[v] = tn[v] = false;
mxs[v] = mxt[v] = rs[v] = rt[v] = inf;
}
for(int i = 0; i < s; i++) {
sn[x[i]] = true;
}
for(int i = 0; i < t; i++) {
tn[y[i]] = true;
}
stack<int> st;
for(int i = 0; i < (int)ver.size(); i++) {
while(!st.empty() && !upper(st.top(), ver[i])) {
st.pop();
}
if(!st.empty()) {
adj[st.top()].push_back({ver[i], d[ver[i]] - d[st.top()]});
}
st.push(ver[i]);
}
// cout << "edges: " << '\n';
// for(auto v : ver) {
// for(auto [to, c] : adj[v]) {
// cout << v << ' ' << to << ' ' << c << '\n';
// }
// }
{
auto dfs = [&](auto &&self, int v) -> void {
if(sn[v]) mxs[v] = d[v];
if(tn[v]) mxt[v] = d[v];
for(auto [to, c] : adj[v]) {
self(self, to);
chmin(mxs[v], mxs[to]);
chmin(mxt[v], mxt[to]);
}
};
dfs(dfs, ver[0]);
}
ll ans = inf;
{
auto dfs = [&](auto &&self, int v) -> void {
if(sn[v]) {
chmin(ans, min(rt[v], mxt[v] - d[v]));
}
if(tn[v]) {
chmin(ans, min(rs[v], mxs[v] - d[v]));
}
int m = adj[v].size();
vector<array<ll, 2>> suf(m + 1, {inf, inf});
for(int i = m - 1; i >= 0; i--) {
auto [to, c] = adj[v][i];
suf[i][0] = min(suf[i + 1][0], mxs[to]);
suf[i][1] = min(suf[i + 1][1], mxt[to]);
}
array<ll, 2> pref{inf, inf};
for(int i = 0; i < m; i++) {
auto [to, c] = adj[v][i];
rs[to] = c + min({rs[v], suf[i + 1][0] - d[v], pref[0] - d[v]});
rt[to] = c + min({rt[v], suf[i + 1][1] - d[v], pref[1] - d[v]});
chmin(pref[0], mxs[to]);
chmin(pref[1], mxt[to]);
self(self, to);
}
};
dfs(dfs, ver[0]);
}
return ans;
}
