#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];
int rmq[1 + lgmax][1 + nmax * 2];
int pos_glob[1 + nmax * 2], glob = 0;
void dfs(int node, int parent, int &acc) {
id[node] = ++acc;
pos_glob[node] = glob++;
rmq[0][glob - 1] = node;
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);
rmq[0][glob++] = node;
}
}
}
int getbest(int x, int y) {
if(level[x] < level[y])
return x;
else
return y;
}
int lg(int x) {
return 31 - __builtin_clz(x);
}
int lca(int x, int y) {
x = pos_glob[x];
y = pos_glob[y];
if(y < x)
std::swap(x, y);
int h = lg(y - x + 1);
return getbest(rmq[h][x], rmq[h][y - (1 << h) + 1]);
}
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 < glob - (1 << h) + 1; i++)
rmq[h][i] = getbest(rmq[h - 1][i], rmq[h - 1][i + (1 << (h - 1))]);
}
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 dp[1 + nmax], dp2[1 + nmax];
void computedp(int node, int parent) {
for(int h = 0; h < secg[node].size(); h++) {
std::pair<int, ll> edge = secg[node][h];
if(edge.first != parent) {
computedp(edge.first, node);
dp[node] = std::min(dp[node], dp[edge.first] + edge.second);
}
}
}
void computedp2(int node, int parent) {
dp2[node] = std::min(dp2[node], dp[node]);
for(int h = 0; h < secg[node].size(); h++) {
std::pair<int, ll> edge = secg[node][h];
if(edge.first != parent) {
dp2[edge.first] = std::min(dp2[edge.first], dp2[node] + edge.second);
computedp2(edge.first, node);
}
}
}
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;
dp[base[i]] = dp2[base[i]] = inf;
}
for(int i = 0; i < fact1.size(); i++)
dp[fact1[i]] = 0;
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]);
}
computedp(base[0], -1);
computedp2(base[0], -1);
ll result = inf;
for(int i = 0; i < fact2.size(); i++)
result = std::min(result, dp2[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);
}
