#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)
// defapt, nu se poate mai bine de centroid???
// asta e doar o fita confirmed???
const int nmax = 5e5 + 5;
vector< pair<int,int> > g[nmax];
namespace LCA {
int father[nmax][19], pin[nmax], pout[nmax], inp, depth[nmax], h[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 < 19; i++)
father[node][i] = father[father[node][i]][i];
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 = 18; i >= 0; i--)
if(!isanc(father[x][i], y))
x = father[x][i];
return father[x][0];
}
int dist(int x, int y) {
return depth[x] + depth[y] - 2 * depth[lca(x, y)];
}
}
struct PartTree {
vector< pair<int,int> > t[nmax];
vector<int> nds;
int color[nmax], dist[nmax];
void addedge(int x, int y, int c) { nds.push_back(x), t[x].push_back({y, c}),
nds.push_back(y), t[y].push_back({x, c}); };
void clear(int x) { dist[x] = 0, color[x] = 0, t[x].clear(); }
priority_queue< pair<int,int>, vector<pair<int,int> >, greater<pair<int,int> > > heap;
#warning VERIFICA SA NU BUSESTI DIJKSTRA-UL SI ACUM PUII MEI
int dijkstra() {
if(heap.empty())
return -1;
int node, cost;
tie(cost, node) = heap.top();
heap.pop();
if(cost > dist[node]) {
return dijkstra();
}
if(color[node] == 2)
return cost;
for(auto [x, c] : t[node]) {
if(dist[x] > dist[node] + c) {
dist[x] = dist[node] + c;
heap.push({dist[x], x});
}
}
return dijkstra();
}
int answer(vector<int> l, vector<int> 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, LCA::dist(lastadded, st.back()));
}
if(lastadded != high)
addedge(high, lastadded, LCA::dist(lastadded, high));
st.push_back(high);
if(high != node)
st.push_back(node);
}
int temp;
while(st.size() > 1) {
temp = st.back(), st.pop_back();
addedge(st.back(), temp, LCA::dist(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<int,int>, vector<pair<int,int> >, greater<pair<int,int> > >();
for(auto x : nds)
clear(x);
nds.clear();
return temp;
}
} ttrick;
#undef int
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<long long> 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]);
return ttrick.answer(l, r);
}
