#include "factories.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N = 5e5 + 5,K = 23,oo = 1e17;
vector<pair<ll,ll>> adj[N + 1];
ll dis[N + 1],fi[N + 1],t = 0;
ll eu[2*N + 1],sparse[2*N + 1][K + 1];
void dfs(ll s,ll pa) {
fi[s] = t;
eu[t] = s;
t++;
for(auto u : adj[s]) {
if(u.first == pa) continue;
dis[u.first] = dis[s] + u.second;
dfs(u.first,s);
eu[t] = s;
t++;
}
}
ll lg[2*N + 1];
void build() {
for(ll i = 2;i <= t;i++) {
lg[i] = lg[i/2] + 1;
}
for(ll i = 0;i < t;i++) {
sparse[i][0] = dis[eu[i]];
}
for(ll j = 1;j <= K;j++) {
for(ll i = 0;i + (1<<j) <= t;i++) {
sparse[i][j] = min(sparse[i][j - 1],sparse[i + (1<<(j - 1))][j - 1]);
}
}
}
ll query(ll l,ll r) {
if(l > r) swap(l,r);
ll len = lg[r - l + 1];
return min(sparse[l][len],sparse[r - (1<<len) + 1][len]);
}
ll lca(ll a,ll b) {
return query(fi[a],fi[b]);
}
ll help_dis(ll a,ll b) {
return dis[a] + dis[b] - 2*lca(a,b);
}
ll cha[N + 1],sz[N + 1];
bool dele[N + 1];
void init(ll s,ll pa) {
sz[s] = 1;
for(auto u : adj[s]) {
if(u.first == pa || dele[u.first]) continue;
init(u.first,s);
sz[s] += sz[u.first];
}
}
ll find_cen(ll s,ll cnt,ll pa) {
for(auto u : adj[s]) {
if(dele[u.first] || u.first == pa) continue;
if(sz[u.first]*2 > cnt) {
return find_cen(u.first,cnt,s);
}
}
return s;
}
void decompose(ll s,ll pa) {
init(s,-1);
ll u = find_cen(s,sz[s],pa);
dele[u] = true;
cha[u] = pa;
for(auto v : adj[u]) {
if(dele[v.first]) continue;
decompose(v.first,u);
}
}
ll dp[N + 1];
void Init(int len, int A[], int B[], int D[]) {
int n = len;
for(int i = 0;i < n - 1;i++) {
adj[A[i]].push_back({B[i],D[i]});
adj[B[i]].push_back({A[i],D[i]});
}
for(int i = 0;i < n;i++) {
fi[i] = oo;
dp[i] = oo;
}
dfs(0,-1);
build();
decompose(0,-1);
}
long long Query(int s, int x[], int t, int y[]) {
for(ll i = 0;i < s;i++) {
ll crr = x[i];
while(crr != -1) {
dp[crr] = min(dp[crr],help_dis(crr,x[i]));
crr = cha[crr];
}
// cout<<endl;
}
ll res = oo;
for(int i = 0;i < t;i++) {
int crr = y[i];
while(crr != -1) {
res = min(res,dp[crr] + help_dis(crr,y[i]));
crr = cha[crr];
// cout<<crr<<" "<<dp[crr]<<" ";
}
// cout<<endl;
}
for(ll i = 0;i < s;i++) {
ll crr = x[i];
while(crr != -1) {
dp[crr] = oo;
crr = cha[crr];
}
}
return res;
}
