#include "factories.h"
#include <vector>
#include <set>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxN = 500'000;
const int logN = 19;
const long long INF = 1'000'000'000'000'000'000LL;
//ZERO-INDEXED!!!
int N;
vector<int> edge[maxN];
vector<long long> wt[maxN];
int curr = -1;
vector<int> order;
vector<int> ind(maxN, -1);
vector<int> depth(maxN, 0);
vector<long long> dist0(maxN, 0);
int** anc;
void dfs(int u)
{
curr++;
ind[u] = curr;
order.push_back(u);
for(int e = 0; e < (int)edge[u].size(); e++)
{
int v = edge[u][e];
long long w = wt[u][e];
if(ind[v] != -1) continue;
depth[v] = depth[u] + 1;
dist0[v] = dist0[u] + w;
anc[v][0] = u;
dfs(v);
}
}
void Init(int N_, int A[], int B[], int D[])
{
N = N_;
for(int e = 0; e < N-1; e++)
{
edge[ A[e] ].push_back( B[e] );
wt[ A[e] ].push_back( D[e] );
edge[ B[e] ].push_back( A[e] );
wt[ B[e] ].push_back( D[e] );
}
anc = new int*[N];
for(int i = 0; i < N; i++) anc[i] = new int[logN];
anc[0][0] = 0;
dfs(0);
for(int e = 1; e < logN; e++)
for(int i = 0; i < N; i++)
anc[i][e] = anc[ anc[i][e-1] ][e-1];
}
int getAnc(int u, int d)
{
for(int e = logN-1; e >= 0; e--)
if((1 << e) & d)
u = anc[u][e];
return u;
}
int lca(int u, int v)
{
if(depth[u] > depth[v]) swap(u, v);
for(int e = logN-1; e >= 0; e--)
if((1 << e) & (depth[v] - depth[u]))
v = anc[v][e];
if(u == v) return u;
for(int e = logN-1; e >= 0; e--)
{
if(anc[u][e] != anc[v][e])
{
u = anc[u][e];
v = anc[v][e];
}
}
u = anc[u][0];
v = anc[v][0];
return u;
}
int S;
vector<int> X;
int T;
vector<int> Y;
vector<int> Z;
vector<int>* new_edge;
vector<long long>* new_wt;
int act(int i) //actual
{
if(i < S) return X[i];
else if(i < S+T) return Y[i-S];
else return Z[i-S-T];
}
void add_new_edge(int u, int v, long long d)
{
new_edge[u].push_back(v);
new_wt[u].push_back(d);
new_edge[v].push_back(u);
new_wt[v].push_back(d);
}
vector<long long> src_dist;
struct pos
{
int i;
};
bool operator < (pos A, pos B)
{
if(src_dist[A.i] == src_dist[B.i]) return A.i < B.i;
return src_dist[A.i] < src_dist[B.i];
}
long long Query(int S_, int X_[], int T_, int Y_[])
{
S = S_;
T = T_;
X = vector<int>(S);
for(int i = 0; i < S; i++) X[i] = X_[i];
Y = vector<int>(T);
for(int i = 0; i < T; i++) Y[i] = Y_[i];
Z.clear();
vector<int> V(S+T);
for(int i = 0; i < S+T; i++) V[i] = i;
sort(V.begin(), V.end(), [] (int i, int j)
{
return ind[act(i)] < ind[act(j)];
});
for(int i = 0; i+1 < S+T; i++)
{
Z.push_back(lca(act(V[i]), act(V[i+1])));
V.push_back(S+T+i);
}
sort(V.begin(), V.end(), [] (int i, int j)
{
return ind[act(i)] < ind[act(j)];
});
int Q = (int)V.size();
new_edge = new vector<int>[Q];
new_wt = new vector<long long>[Q];
vector<int> st(1, V[0]);
for(int i = 1; i < Q; i++)
{
while(act(st.back()) != getAnc(act(V[i]), depth[act(V[i])] - depth[act(st.back())]))
st.pop_back();
add_new_edge(V[i], st.back(), dist0[act(V[i])] - dist0[act(st.back())]);
st.push_back(V[i]);
}
src_dist = vector<long long>(Q, INF);
for(int i = 0; i < S; i++) src_dist[i] = 0;
set<pos> tbv;
for(int i = 0; i < Q; i++) tbv.insert(pos{i});
while(!tbv.empty())
{
int u = tbv.begin()->i;
tbv.erase(tbv.begin());
for(int e = 0; e < (int)new_edge[u].size(); e++)
{
int v = new_edge[u][e];
long long w = new_wt[u][e];
if(src_dist[v] > src_dist[u] + w)
{
tbv.erase(pos{v});
src_dist[v] = src_dist[u] + w;
tbv.insert(pos{v});
}
}
}
long long res = INF;
for(int i = S; i < S+T; i++)
res = min(res, src_dist[i]);
X.clear();
Y.clear();
Z.clear();
src_dist.clear();
for(int i = 0; i < Q; i++)
{
new_edge[i].clear();
new_wt[i].clear();
}
return res;
}
