#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, dist[MAXN];
bool visited[MAXN], isY[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 isAncestor(int u, int v) {
return tin[u] <= tin[v] && tout[u] >= tout[v];
}
int LCA(int u, int v) {
if(isAncestor(u, v)) return u;
if(isAncestor(v, u)) return v;
for(int i = 17; i >= 0; i--) {
if(!isAncestor(par[u][i], v)) u = par[u][i];
}
return par[u][0];
}
long long getDist(int u, int v) {
int lca = LCA(u, v);
return dist[u] + dist[v] - 2 * dist[lca];
}
void Init(int n, int A[], int B[], int D[]) {
for(int i = 0; i < n - 1; i++) {
adj[A[i]].emplace_back(B[i], D[i]);
adj[B[i]].emplace_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]);
isY[Y[i]] = true;
}
sort(nodes.begin(), nodes.end(), [](int u, int v) { return tin[u] < tin[v]; });
vector<int> allNodes = nodes;
for(int i = 1; i < nodes.size(); i++) {
allNodes.push_back(LCA(nodes[i - 1], nodes[i]));
}
sort(allNodes.begin(), allNodes.end(), [](int u, int v) { return tin[u] < tin[v]; });
allNodes.erase(unique(allNodes.begin(), allNodes.end()), allNodes.end());
stack<int> st;
st.push(allNodes[0]);
for(int i = 1; i < allNodes.size(); i++) {
int u = allNodes[i];
while(!isAncestor(st.top(), u)) st.pop();
int v = st.top();
long long d = getDist(u, v);
vt[u].emplace_back(v, d);
vt[v].emplace_back(u, d);
st.push(u);
}
priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> pq;
for(int i = 0; i < S; i++) {
pq.emplace(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(isY[u]) {
res = d;
break;
}
for(auto [v, w] : vt[u]) {
if(!visited[v]) pq.emplace(d + w, v);
}
}
for(int u : allNodes) {
vt[u].clear();
visited[u] = false;
isY[u] = false;
}
return res;
}
