#include "factories.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb emplace_back
#define mp make_pair
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
const int N = 5e5 + 13, L = 20;
const ll inf = 1LL << 60;
ll d[N];
int p[N], dep[N], sz[N];
vector<pii> G[N];
int timer = 0, timer2 = 0, op[N * 2], ed[N * 2], op2[N * 2], ed2[N * 2];
int euler[N], euler2[N * 2];
int st[N][L];
int n;
void dfs(int v, int par = -1){
euler[timer] = v, op[v] = timer++, sz[v] = 1;
euler2[timer2] = v, op2[v] = timer2++;
int out = 0, son = -1;
for(auto i : G[v]){
if(i.fi != par){
d[i.fi] = d[v] + i.se;
p[i.fi] = v;
dep[i.fi] = dep[v] + 1;
dfs(i.fi, v);
euler2[timer2++] = v;
out++; son = i.fi;
sz[v] += sz[i.fi];
}
}
ed[v] = timer;
ed2[v] = timer2 - 1;
}
struct Fenwick{
ll bit[N];
void upd(int p, ll v){
p++;
for(int i = p; i < N; i += i & -i){
bit[i] += v;
}
}
int qry(int p){
p++;
int ret = 0;
for(int i = p; i; i -= i & -i){
ret += bit[i];
}
return ret;
}
int qry_pos(int v){ // 1-base, >= 1
ll ret = 0, val = 0;
for(int j = 19; j >= 0; j--){
if(ret + (1 << j) >= N) continue;
if(val + bit[ret + (1 << j)] < v) val += bit[ret + (1 << j)], ret += (1 << j);
}
return ret;
}
} c0, c1;
void bl(int n){
for(int i = 0; i < n * 2 - 1; i++) st[i][0] = euler2[i];
for(int j = 1; j < 20; j++){
for(int i = 0; i <= n * 2 - 1 - (1 << j); i++){
st[i][j] = dep[st[i][j - 1]] < dep[st[i + (1 << j - 1)][j - 1]] ? st[i][j - 1] : st[i + (1 << j - 1)][j - 1];
}
}
}
int lca(int x, int y){
int a = min(op2[x], op2[y]), b = max(ed2[x], ed2[y]);
int l = __lg(b - a + 1);
int ret = dep[st[a][l]] < dep[st[b - (1 << l) + 1][l]] ? st[a][l] : st[b - (1 << l) + 1][l];
return ret;
}
struct state{
int v; ll dis; int colour;
state(){};
state(int v, ll d, int c) : v(v), dis(d), colour(c){};
bool operator< (const state& o) const{
return v < o.v;
}
};
ll dp[N][2];
void Init(int32_t N, int32_t A[], int32_t B[], int32_t D[]) {
n = N;
for(int i = 0; i < N - 1; i++){
G[B[i]].pb(A[i], D[i]);
G[A[i]].pb(B[i], D[i]);
}
dfs(0);
bl(N);
for(int i = 0; i < n; i++){
dp[i][0] = dp[i][1] = inf;
}
for(int i = 0; i < N; i++){
G[i].resize(0);
}
}
struct cmp{
bool operator() (const int u, const int v){
return dep[u] < dep[v];
}
};
bool in_pq[N];
long long Query(int32_t S, int32_t X[], int32_t T, int32_t Y[]) {
for(int j = 0; j < S; j++) c0.upd(op[X[j]], 1);
for(int j = 0; j < T; j++) c1.upd(op[Y[j]], 1);
ll ans = inf;
priority_queue<int, vector<int>, cmp> pq;
for(int j = 0; j < S; j++){
pq.push(X[j]);
in_pq[X[j]] = true;
}
for(int j = 0; j < T; j++){
pq.push(Y[j]);
in_pq[Y[j]] = true;
}
for(int j = 0; j < S; j++) dp[X[j]][0] = 0;
for(int j = 0; j < T; j++) dp[Y[j]][1] = 0;
int j = -1;
vector<int> reach;
for(j; pq.size();){
j = pq.top(); pq.pop(); in_pq[j] = false;
reach.pb(j);
if(j > 0){
if(dp[j][1] != inf){
int _lca = 0;
int l = c0.qry_pos(c0.qry(op[j] - 1)), r = c0.qry_pos(c0.qry(op[j] + sz[j] - 1) + 1);
if(l < 0 && r > n - 1) _lca = 0;
else if(l < 0 || r > n - 1) _lca = l < 0 ? lca(j, euler[r]) : lca(euler[l], j);
else{
int llca = lca(euler[l], j), rlca = lca(j, euler[r]);
_lca = (dep[llca] > dep[rlca] ? llca : rlca);
}
if(_lca == j) _lca = p[j];
if(!in_pq[_lca]) in_pq[_lca] = true, dp[_lca][0] = dp[_lca][1] = inf, pq.push(_lca);
ll new_dis = dp[j][1] + d[j] - d[_lca];
ans = min(ans, dp[_lca][0] + new_dis);
dp[_lca][1] = min(dp[_lca][1], new_dis);
}
if(dp[j][0] != inf){
int _lca = 0;
int l = c1.qry_pos(c1.qry(op[j] - 1)), r = c1.qry_pos(c1.qry(op[j] + sz[j] - 1) + 1);
if(l < 0 && r > n - 1) _lca = 0;
else if(l < 0 || r > n - 1) _lca = l < 0 ? lca(j, euler[r]) : lca(euler[l], j);
else{
int llca = lca(euler[l], j), rlca = lca(j, euler[r]);
_lca = (dep[llca] > dep[rlca] ? llca : rlca);
}
if(_lca == j) _lca = p[j];
if(!in_pq[_lca]) in_pq[_lca] = true, dp[_lca][0] = dp[_lca][1] = inf, pq.push(_lca);
ll new_dis = dp[j][0] + d[j] - d[_lca];
ans = min(ans, dp[_lca][1] + new_dis);
dp[_lca][0] = min(dp[_lca][0], new_dis);
}
}
}
for(auto i : reach){
dp[i][0] = dp[i][1] = inf;
}
for(int j = 0; j < S; j++) c0.upd(op[X[j]], -1);
for(int j = 0; j < T; j++) c1.upd(op[Y[j]], -1);
return ans;
}
