#include "factories.h"
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;
const int MAXN = 5e5 + 5;
const long long INF = 1e18;
vector<pair<int, int>> adj[MAXN];
vector<pair<int, long long>> vt[MAXN];
int depth[MAXN], par[MAXN][20];
long long tin[MAXN], tout[MAXN], timer;
long long dist[MAXN];
bool visited[MAXN];
long long dp[MAXN];
void dfs(int u, int p) {
par[u][0] = p;
tin[u] = ++timer;
for (int i = 1; i <= 17; i++) {
par[u][i] = par[par[u][i - 1]][i - 1];
}
for (auto [v, w] : adj[u]) {
if (v == p) continue;
depth[v] = depth[u] + 1;
dist[v] = dist[u] + w;
dfs(v, u);
}
tout[u] = timer;
}
bool check(int u, int v) {
return tin[u] <= tin[v] && tout[u] >= tout[v];
}
int lca(int u, int v) {
if (check(u, v)) return u;
if (check(v, u)) return v;
for (int i = 17; i >= 0; i--) {
if (depth[u] - (1 << i) >= 0 && !check(par[u][i], v)) {
u = par[u][i];
}
}
return par[u][0];
}
long long get_dist(int u, int v) {
int ancestor = lca(u, v);
return dist[u] + dist[v] - 2 * dist[ancestor];
}
void Init(int n, int A[], int B[], int D[]) {
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]});
}
dfs(0, 0);
}
long long Query(int S, int X[], int T, int Y[]) {
vector<int> nodes;
for (int i = 0; i < S; i++) nodes.push_back(X[i]);
for (int i = 0; i < T; i++) {
nodes.push_back(Y[i]);
dp[Y[i]] = 0;
}
sort(nodes.begin(), nodes.end(), [](int u, int v) { return tin[u] < tin[v]; });
vector<int> all = nodes;
for (int i = 1; i < nodes.size(); i++) {
all.push_back(lca(nodes[i - 1], nodes[i]));
}
sort(all.begin(), all.end(), [](int u, int v) { return tin[u] < tin[v]; });
all.erase(unique(all.begin(), all.end()), all.end());
stack<int> st;
st.push(all[0]);
for (int i = 1; i < all.size(); i++) {
int u = all[i];
while (!check(st.top(), u)) st.pop();
int v = st.top();
long long d = get_dist(u, v);
vt[u].push_back({v, d});
vt[v].push_back({u, d});
st.push(u);
}
priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
for (int i = 0; i < S; i++) {
pq.push({0, X[i]});
}
long long res = INF;
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
if (visited[u]) continue;
visited[u] = true;
if (dp[u] == 0) {
res = d;
break;
}
for (auto [v, w] : vt[u]) {
if (!visited[v]) pq.push({d + w, v});
}
}
for (int u : all) {
vt[u].clear();
visited[u] = false;
dp[u] = INF;
}
return res;
}
