#include "factories.h"
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define all(v) begin(v), end(v)
#define pi pair<int, int>
#define vi vector<int>
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll rd(ll l, ll r){
return rng() % (r-l+1) + l;
}
const int N = 5e5+3;
int n, q;
vector<pair<int, ll>> g[N], g2[N];
int tin[N], tout[N] = {500069}, timer;
ll pf[N];
int sp[N][20];
void dfs(int u, int p){
for(int i = 1; i <= 19; i++) sp[u][i] = sp[sp[u][i-1]][i-1];
tin[u] = ++timer;
for(auto [v, w]:g[u]){
if(v == p) continue;
sp[v][0] = u;
pf[v] = pf[u] + w;
dfs(v, u);
}
tout[u] = timer;
}
int lca(int u, int v){
if(tin[u] <= tin[v] && tout[v] <= tout[u]) return u;
for(int i = 19; i >= 0; i--){
if(!(tin[sp[u][i]] <= tin[v] && tout[v] <= tout[sp[u][i]])){
u = sp[u][i];
}
}
return sp[u][0];
}
int c[N];
bool vis[N];
pair<ll, ll> dis[N];
ll ans = 0;
void dfs2(int u, int p){
if(c[u] == 1) dis[u].first = 0;
else if(c[u] == 2) dis[u].second = 0;
for(auto [v, w]:g2[u]){
if(v == p) continue;
dfs2(v, u);
dis[u].first = min(dis[u].first, dis[v].first + w);
dis[u].second = min(dis[u].second, dis[v].second + w);
}
ans = min(ans, dis[u].first + dis[u].second);
return ;
}
void Init(int N, int A[], int B[], int D[]){
n = N;
for(int i = 0; i < n-1; i++){
g[A[i]+1].push_back({B[i]+1, D[i]});
g[B[i]+1].push_back({A[i]+1, D[i]});
}
dfs(1, 0);
memset(dis, 0x3f, sizeof(dis));
return ;
}
long long Query(int s, int X[], int t, int Y[]){
vector<int> v;
for(int i = 0; i < s; i++){
v.push_back(X[i]+1);
c[X[i]+1] = 1;
}
for(int i = 0; i < t; i++){
v.push_back(Y[i]+1);
c[Y[i]+1] = 2;
}
sort(all(v), [&](int a, int b){
return tin[a] < tin[b];
});
vector<int> t2;
for(int i = 0; i < s+t-1; i++){
t2.push_back(v[i]);
t2.push_back(lca(v[i], v[i+1]));
}
t2.push_back(v[s+t-1]);
sort(all(t2)); t2.erase(unique(all(t2)), t2.end());
sort(all(t2), [&](int a, int b){
return tin[a] < tin[b];
});
vector<int> nx(t2.size()+1);
for(int i = t2.size()-1; i >= 0; i--){
int l = i+1, r = t2.size() - 1;
while(l <= r){
int mid = (l+r)/2;
if(tin[t2[mid]] <= tout[t2[i]]) l = mid+1;
else r = mid-1;
}
nx[i] = l;
}
for(int i = t2.size() - 1; i >= 0; i--){
for(int j = i+1; j <= nx[i]-1;){
g2[t2[i]].push_back({t2[j], pf[t2[j]] - pf[t2[i]]});
j = nx[j];
}
}
ans = 4e18;
for(auto x:t2){
if(!vis[x]) dfs2(x, 0);
}
for(auto x:t2){
g2[x].clear();
vis[x] = false;
c[x] = 0;
dis[x] = {1e18, 1e18};
}
t2.clear();
return ans;
}
// #define MAX_N 500000
// #define MAX_Q 100000
// #define MAX_SUM_ST 1000000
// #define MAX_VALUE 1000000000
// static int NN, Q;
// static int A[MAX_N], B[MAX_N], D[MAX_N];
// static int S[MAX_N];
// static int T[MAX_N];
// static int X[MAX_SUM_ST];
// static int Y[MAX_SUM_ST];
// static int Qx[MAX_N];
// static int Qy[MAX_N];
// int main() {
// int i, j, k;
// int STop, TTop;
// if (2 != scanf("%d%d", &NN, &Q)) {
// fprintf(stderr, "error: cannot read N and Q.\n");
// exit(1);
// }
// if (!(2 <= NN && NN <= MAX_N)) {
// fprintf(stderr, "error: N is out of bounds.\n");
// exit(1);
// }
// if (!(1 <= Q && Q <= MAX_Q)) {
// fprintf(stderr, "error: Q is out of bounds.\n");
// exit(1);
// }
// for (i = 0; i < NN - 1; ++i) {
// if (1 != scanf("%d", &A[i])) {
// fprintf(stderr, "error: cannot read A[%d].\n", i);
// exit(1);
// }
// if (!(0 <= A[i] && A[i] <= NN - 1)) {
// fprintf(stderr, "error: A[%d] is out of bounds.\n", i);
// exit(1);
// }
// if (1 != scanf("%d", &B[i])) {
// fprintf(stderr, "error: cannot read B[%d].\n", i);
// exit(1);
// }
// if (!(0 <= B[i] && B[i] <= NN - 1)) {
// fprintf(stderr, "error: B[%d] is out of bounds.\n", i);
// exit(1);
// }
// if (A[i] == B[i]) {
// fprintf(stderr, "error: B[%d] is equal to A[%d].\n", i, i);
// exit(1);
// }
// if (1 != scanf("%d", &D[i])) {
// fprintf(stderr, "error: cannot read D[%d].\n", i);
// exit(1);
// }
// if (!(1 <= D[i] && D[i] <= MAX_VALUE)) {
// fprintf(stderr, "error: D[%d] is out of bounds.\n", i);
// exit(1);
// }
// }
// STop = 0;
// TTop = 0;
// for (j = 0; j < Q; ++j) {
// if (2 != scanf("%d%d", &S[j], &T[j])) {
// fprintf(stderr, "error: cannot read L[%d] and R[%d].\n", j, j);
// exit(1);
// }
// if(STop + S[j] > MAX_SUM_ST) {
// fprintf(stderr, "error: S[0] + S[1] + ... + S[%d] is out of bounds.\n", j);
// exit(1);
// }
// if(TTop + T[j] > MAX_SUM_ST) {
// fprintf(stderr, "error: T[0] + T[1] + ... + T[%d] is out of bounds.\n", j);
// exit(1);
// }
// for (k = 0; k < S[j]; ++k, ++STop) {
// if (1 != scanf("%d", &X[STop])) {
// fprintf(stderr, "error: cannot read X[%d][%d].\n", j, k);
// exit(1);
// }
// if (!(0 <= X[STop] && X[STop] <= NN - 1)) {
// fprintf(stderr, "error: cannot read X[%d][%d].\n", j, k);
// exit(1);
// }
// }
// for (k = 0; k < T[j]; ++k, ++TTop) {
// if (1 != scanf("%d", &Y[TTop])) {
// fprintf(stderr, "error: cannot read Y[%d][%d].\n", j, k);
// exit(1);
// }
// if (!(0 <= Y[TTop] && Y[TTop] <= NN - 1)) {
// fprintf(stderr, "error: cannot read Y[%d][%d].\n", j, k);
// exit(1);
// }
// }
// }
// STop = 0;
// TTop = 0;
// Init(NN, A, B, D);
// for (j = 0; j < Q; ++j) {
// for (k = 0; k < S[j]; k++) {
// Qx[k] = X[STop++];
// }
// for (k = 0; k < T[j]; k++) {
// Qy[k] = Y[TTop++];
// }
// printf("%lld\n", Query(S[j], Qx, T[j], Qy));
// }
// return 0;
// }
