#include "factories.h"
#include <bits/stdc++.h>
//#define int long long
// Solutie: LCA Tree + Dijkstra
using namespace std; // asta e pentru &u' (ca poate bagam centroid decomp idk)
using ll = long long;
// defapt, nu se poate mai bine de centroid???
// asta e doar o fita confirmed???
const int nmax = 5e5 + 5;
vector< pair<int,ll> > g[nmax];
//#define int ll
namespace LCA {
int father[nmax][21], pin[nmax], pout[nmax], inp, h[nmax];
ll depth[nmax];
auto bypin = [](int a, int b) { return pin[a] < pin[b];};
void init(int node = 0, int f = 0) {
pin[node] = inp++;
father[node][0] = f;
h[node] = h[f] + 1;
for(int i = 1; i < 21; i++)
father[node][i] = father[father[node][i - 1]][i - 1];
for(auto [x, c] : g[node]) {
if(x != f)
depth[x] = depth[node] + c, init(x, node);
}
pout[node] = inp - 1;
}
bool isanc(int f, int node) { return pin[f] <= pin[node] && pout[node] <= pout[f]; }
int lca(int x, int y) {
if(isanc(x, y))
return x;
if(isanc(y, x))
return y;
for(int i = 20; i >= 0; i--)
if(!isanc(father[x][i], y))
x = father[x][i];
return father[x][0];
}
ll dist(int x, int y) {
int l = lca(x, y);
return depth[x] + depth[y] - 2 * depth[l];
}
}
//#undef int
struct PartTree {
vector< int > t[nmax];
vector<int> nds;
char color[nmax];
ll dist[nmax];
void addedge(int x, int y) {nds.push_back(x), t[x].push_back(y),
nds.push_back(y), t[y].push_back(x); };
void clear(int x) { dist[x] = 0, color[x] = 0, t[x].clear(); }
priority_queue< pair<ll,int>, vector<pair<ll,int> >, greater<pair<ll,int> > > heap;
#warning VERIFICA SA NU BUSESTI DIJKSTRA-UL SI ACUM PUII MEI
ll dijkstra() {
if(heap.empty())
assert(false);
int node;
ll cost;
tie(cost, node) = heap.top();
heap.pop();
if(cost > dist[node]) {
return dijkstra();
}
if(color[node] == 2)
return cost;
#define int ll
for(auto x : t[node]) {
ll c = LCA::dist(node, x);
if(dist[x] > dist[node] + c) {
dist[x] = dist[node] + c;
assert(dist[node] + c > 0);
heap.push({dist[x], x});
}
}
#undef int
return dijkstra();
}
ll answer(vector<signed> l, vector<signed> r) {
vector<int>list;
for(auto x : l)
color[x] = 1, list.push_back(x);
for(auto y : r)
color[y] = 2, list.push_back(y);
sort(list.begin(), list.end(), LCA::bypin);
vector<int> st;
for(auto node : list) {
if(st.empty()) {
st.push_back(node);
continue;
}
int high = LCA::lca(node, st.back());
int lastadded = high;
while(!st.empty() && LCA::h[st.back()] >= LCA::h[high]) {
lastadded = st.back();
st.pop_back();
if(!st.empty() && !(LCA::h[st.back()] < LCA::h[high]))
addedge(st.back(), lastadded);
}
if(lastadded != high)
addedge(high, lastadded);
st.push_back(high);
if(high != node)
st.push_back(node);
}
ll temp;
while(st.size() > 1) {
temp = st.back(), st.pop_back();
addedge(st.back(), temp);
}
sort(nds.begin(), nds.end());
nds.resize(distance(nds.begin(), unique(nds.begin(), nds.end())));
for(auto x : nds)
if(color[x] == 1)
heap.push({0, x});
else
dist[x] = 5e13L + 5LL;
temp = dijkstra();
heap = priority_queue< pair<ll,int>, vector<pair<ll,int> >, greater<pair<ll,int> > >();
for(auto x : nds)
clear(x);
nds.clear();
return temp;
}
//#undef int
} ttrick;
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]});
LCA::init();
}
long long Query(int S, int X[], int T, int Y[]) {
vector<int> l, r;
for(int i = 0; i < S; i++)
l.push_back(X[i]);
for(int i = 0; i < T; i++)
r.push_back(Y[i]);
ll o = ttrick.answer(l, r);
return o;
}
