#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int LG = 20;
struct lcasparse{
vector<pair<ll, int>> a[LG];
vector<int> tin;
vector<int> tout;
void add_node(ll d, int v){
if (tin[v] == -1) tin[v] = a[0].size();
a[0].emplace_back(d, v);
}
void mark_out(int v){
tout[v] = a[0].size()-1;
}
void lock(){
for (int i=1; i<LG; i++){
a[i].resize(a[0].size());
for (int j=0; j + (1<<(i-1)) < a[i].size(); j++){
a[i][j] = min(a[i-1][j], a[i-1][j + (1<<(i-1))]);
}
}
}
int query(int u, int v){
if (tin[u] > tin[v]) swap(u, v);
int lg2 = 31 - __builtin_clz(tin[v] - tin[u] + 1);
return min(a[lg2][tin[u]], a[lg2][tin[v] - (1<<lg2) + 1]).second;
}
void init(int n){
tin.resize(n, -1);
tout.resize(n, -1);
}
ll get_depth(int v){
return a[0][tin[v]].first;
}
bool is_par(int p, int v){
return tin[p] <= tin[v] && tin[v] <= tout[p];
}
} lca;
vector<vector<pair<int, ll>>> g;
void dfslca(int v, int p, ll d){
lca.add_node(d, v);
for (auto [u, ed]: g[v]){
if (u == p) continue;
dfslca(u, v, ed + d);
lca.add_node(d, v);
}
lca.mark_out(v);
}
void Init(int N, int A[], int B[], int D[]){
g.resize(N);
for (int i=0; i<N-1; i++){
int u = A[i], v = B[i];
int d = D[i];
g[u].emplace_back(v, d);
g[v].emplace_back(u, d);
}
lca.init(N);
dfslca(0, -1, 0);
lca.lock();
}
struct testcase{
vector<int> &from, &to;
vector<bool> is_src;
vector<int> nodes;
void get_nodes(){
for (int i=nodes.size()-1; i; i--){
nodes.push_back(lca.query(nodes[i-1], nodes[i]));
}
sort(nodes.begin(), nodes.end(), [](int &a, int &b){
return lca.tin[a] < lca.tin[b];
});
nodes.resize(unique(nodes.begin(), nodes.end()) - nodes.begin());
}
vector<vector<pair<int, ll>>> vtr;
void build_tree(){
vtr.resize(nodes.size());
// rid, vid
vector<pair<int, int>> st;
for (int i=0; i < nodes.size(); i++){
int v = nodes[i];
while (st.size() && !lca.is_par(st.back().first, v)){
st.pop_back();
}
if (st.size()){
vtr[st.back().second].emplace_back(i,
lca.get_depth(v) - lca.get_depth(st.back().first));
}
st.emplace_back(v, i);
}
}
vector<ll> dp;
void dfs1(int v, int p){
if (is_src[v] == 1) dp[v] = 0;
else dp[v] = 1e15;
for (pair<int, ll> e: vtr[v]){
assert((e.first != p));
dfs1(e.first, v);
dp[v] = min(dp[v], dp[e.first] + e.second);
}
}
void dfs2(int v, int p){
for (pair<int, ll> e: vtr[v]){
dp[e.first] = min(dp[e.first], dp[v] + e.second);
dfs2(e.first, v);
}
}
ll result = LLONG_MAX;
void mark_src(){
sort(from.begin(), from.end(), [](int &a, int &b){
return lca.tin[a] < lca.tin[b];
});
is_src.resize(nodes.size());
for (int nptr = 0, i=0; i < from.size(); i++){
while (nodes[nptr] != from[i]) nptr++;
is_src[nptr] = 1;
}
}
void get_result(){
result = LLONG_MAX;
sort(to.begin(), to.end(), [](int &a, int &b){
return lca.tin[a] < lca.tin[b];
});
is_src.resize(nodes.size());
for (int nptr = 0, i=0; i < to.size(); i++){
while (nodes[nptr] != to[i]) nptr++;
result = min(result, dp[nptr]);
}
}
testcase(vector<int> &from, vector<int> &to): from(from), to(to) {
nodes = to;
for (int v: from){
nodes.push_back(v);
}
sort(nodes.begin(), nodes.end(), [](int &a, int &b){
return lca.tin[a] < lca.tin[b];
});
get_nodes();
mark_src();
build_tree();
dp.resize(nodes.size());
dfs1(0, -1);
dfs2(0, -1);
get_result();
}
};
ll Query(int S, int X[], int T, int Y[]){
vector<int> from(X, X + S);
vector<int> to(Y, Y + T);
return testcase(from, to).result;
}
