#include "factories.h"
#include <vector>
#include <algorithm>
#include <cassert>
#include <cmath>
#include <queue>
#include <stack>
#include <iostream>
using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))
int const nmax = 500000;
int const lgmax = 20;
ll const inf = 1000000000000000000;
std::vector<std::pair<int,int>> g[1 + nmax];
int far[1 + lgmax][1 + nmax];
int id[1 + nmax], level[1 + nmax];
ll dist[1 + nmax];
void dfs(int node, int parent, int &acc) {
id[node] = ++acc;
for(int h = 0; h < g[node].size(); h++) {
std::pair<int,int> edge = g[node][h];
if(edge.first != parent) {
level[edge.first] = level[node] + 1;
far[0][edge.first] = node;
dist[edge.first] = dist[node] + edge.second;
dfs(edge.first, node, acc);
}
}
}
int lca(int x, int y) {
if(level[x] < level[y])
std::swap(x, y);
for(int h = lgmax; 0 <= h; h--)
if(level[y] + (1 << h) <= level[x])
x = far[h][x];
if(x == y)
return x;
for(int h = lgmax; 0 <= h; h--)
if(far[h][x] != far[h][y]) {
x = far[h][x];
y = far[h][y];
}
return far[0][x];
}
int isanc(int x, int y) {
return lca(x, y) == x;
}
ll getdist(int x, int y) {
return dist[x] + dist[y] - 2 * dist[lca(x, y)];
}
void Init(int N, int A[], int B[], int D[]) {
for(int i = 0; i < N - 1; i++) {
g[A[i]].push_back({B[i], D[i]});
g[B[i]].push_back({A[i], D[i]});
}
int acc = 0;
dfs(0, -1, acc);
for(int h = 1; h <= lgmax; h++)
for(int i = 0;i < N; i++)
far[h][i] = far[h - 1][far[h - 1][i]];
}
bool compare(int x, int y) {
return id[x] < id[y];
}
std::vector<std::pair<int,ll>> secg[1 + nmax];
ll dist1[1 + nmax];
ll solve(std::vector<int> base, std::vector<int> fact1, std::vector<int> fact2) {
for(int i = 0; i < base.size(); i++) {
secg[base[i]].clear();
dist1[base[i]] = inf;
}
std::stack<int> st;
for(int i = 0; i < base.size(); i++) {
while(0 < st.size() && isanc(st.top(), base[i]) == 0)
st.pop();
if(0 < st.size()) {
ll travel = getdist(st.top(), base[i]);
secg[st.top()].push_back({base[i], travel});
secg[base[i]].push_back({st.top(), travel});
}
st.push(base[i]);
}
std::priority_queue<std::pair<ll,int>, std::vector<std::pair<ll,int>>, std::greater<std::pair<ll, int>>> pq;
for(int i = 0; i < fact1.size(); i++) {
dist1[fact1[i]] = 0;
pq.push({0, fact1[i]});
}
while(0 < pq.size()) {
std::pair<ll, int> pqtop = pq.top();
pq.pop();
if(pqtop.first == dist1[pqtop.second]) {
int node = pqtop.second;
for(int h = 0; h < secg[node].size(); h++) {
std::pair<int, ll> edge = secg[node][h];
if(dist1[node] + edge.second < dist1[edge.first]){
dist1[edge.first] = dist1[node] + edge.second;
pq.push({dist1[edge.first], edge.first});
}
}
}
}
ll result = inf;
for(int i = 0; i < fact2.size(); i++)
result = std::min(result, dist1[fact2[i]]);
return result;
}
long long Query(int S, int X[], int T, int Y[]) {
std::vector<int> base;
for(int i = 0; i < S; i++)
base.push_back(X[i]);
for(int i = 0; i < T; i++)
base.push_back(Y[i]);
std::sort(base.begin(), base.end(), compare);
std::vector<int> aux = base;
for(int i = 1; i < base.size(); i++)
aux.push_back(lca(base[i - 1], base[i]));
std::sort(aux.begin(), aux.end(), compare);
aux.erase(std::unique(aux.begin(), aux.end()), aux.end());
std::vector<int> fact1, fact2;
for(int i = 0; i < S; i++)
fact1.push_back(X[i]);
for(int i = 0; i < T; i++)
fact2.push_back(Y[i]);
return solve(aux, fact1, fact2);
}
