#include "factories.h"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define ii pair<ll,ll>
#define fi first
#define se second
#define all(a) a.begin(),a.end()
using namespace std;
const int N = 5e5 + 5;
const ll inf = 1e18;
const int LOG = 20;
vector<pair<int, int>> adj[N];
vector<ii> v[N]; // virtual tree
int up[N][LOG];
int depth[N];
ll dist[N];
ll tin[N], tout[N], timer = 0;
ll dp[N];
bool visited[N];
void dfs(int u, int p) {
up[u][0] = p;
for (int i = 1; i < LOG; i++) {
up[u][i] = up[up[u][i - 1]][i - 1];
}
tin[u] = ++timer;
for (auto [to, w] : adj[u]) {
if (to != p) {
depth[to] = depth[u] + 1;
dist[to] = dist[u] + w;
dfs(to, u);
}
}
tout[u] = timer;
}
int lca(int u, int v) {
if (depth[u] < depth[v]) swap(u, v);
for (int i = LOG - 1; i >= 0; i--)
if (up[u][i] != -1 && depth[up[u][i]] >= depth[v])
u = up[u][i];
if (u == v) return u;
for (int i = LOG - 1; i >= 0; i--) {
if (up[u][i] != -1 && up[u][i] != up[v][i]) {
u = up[u][i];
v = up[v][i];
}
}
return up[u][0];
}
ll get_dist(int u, int v) {
int ancestor = lca(u, v);
return dist[u] + dist[v] - 2 * dist[ancestor];
}
bool sort_tin(const ll &a, const ll &b) {
return tin[a] < tin[b];
}
bool is_ancestor(ll u, ll v) {
return (tin[u] <= tin[v] && tout[v] <= tout[u]);
}
void Init(int n, int A[], int B[], int D[]) {
for (int i = 0; i < n - 1; i++) {
adj[A[i]].pb({B[i], D[i]});
adj[B[i]].pb({A[i], D[i]});
}
for (int i = 0; i < LOG; i++) up[0][i] = 0;
depth[0] = 0;
dist[0] = 0;
dfs(0, 0);
memset(dp,-1,sizeof(dp));
}
long long Query(int S, int X[], int T, int Y[]) {
vector<ll> special;
for (int i = 0; i < S; i++) special.pb(X[i]);
for (int i = 0; i < T; i++) {
special.pb(Y[i]);
dp[Y[i]] = 0;
}
sort(all(special), sort_tin);
vector<ll> node = special;
for (int i = 1; i < special.size(); i++) {
node.pb(lca(special[i - 1], special[i]));
}
sort(all(node), sort_tin);
node.erase(unique(all(node)), node.end());
stack<ll> st;
st.push(node[0]);
for (int i = 1; i < node.size(); i++) {
ll u = node[i];
while (!is_ancestor(st.top(), u)) st.pop();
ll x = st.top();
ll d = get_dist(u, x);
v[u].pb({x, d});
v[x].pb({u, d});
st.push(u);
}
priority_queue<ii, vector<ii>, greater<ii>> pq;
for (int i = 0; i < S; i++) pq.push({0, X[i]});
ll ans = inf;
while (!pq.empty()) {
auto [d, u] = pq.top(); pq.pop();
// cout<<d<<" "<<u<<'\n';
if (dp[u] == 0) {
ans = d;
break;
}
if (visited[u]) continue;
visited[u] = true;
for (auto [to, w] : v[u]) {
pq.push({d + w, to});
}
}
for (auto u : node) {
v[u].clear();
visited[u] = 0;
dp[u] = -1;
}
return ans;
}
