#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAXN = 5e5 + 5;
const ll INF = 1e16;
#define f first
#define s second
ll centro[MAXN],sz[MAXN],ans,st[MAXN];
vector <pair<ll,ll>> g[MAXN];
vector <ll> h[MAXN];
bool vis[MAXN];
void dfs(ll nodo, ll p, ll height, ll caso) {
if (caso!=0) h[nodo].push_back(height);
sz[nodo] = 1;
for (auto it=g[nodo].begin();it!=g[nodo].end();it++) {
if (it->f!=p && vis[it->f]==false) {
dfs(it->f,nodo,height + it->s,caso);
sz[nodo] += sz[it->f];
}
}
return;
}
ll find_centro(ll nodo, ll p, ll tot) {
for (auto it=g[nodo].begin();it!=g[nodo].end();it++) {
if (it->f!=p && vis[it->f]==false && sz[it->f]*2>tot) {
return find_centro(it->f,nodo,tot);
}
}
return nodo;
}
void decomp(ll nodo, ll p, ll pre) {
nodo = find_centro(nodo,p,sz[nodo]);
vis[nodo] = true;
centro[nodo] = pre;
for (auto it=g[nodo].begin();it!=g[nodo].end();it++) {
if (vis[it->f]==false) {
dfs(it->f,nodo,it->s,1);
decomp(it->f,nodo,nodo);
}
}
return;
}
void limpia(ll nodo) {
while (nodo!=0) {
st[nodo] = INF;
nodo = centro[nodo];
}
return;
}
void update(ll nodo) {
ll aux = centro[nodo], cnt = 0;
if (!h[nodo].empty()) cnt = h[nodo].size()-1;
st[nodo] = 0;
while (aux!=0) {
st[aux] = min(h[nodo][cnt],st[aux]);
cnt--;
aux = centro[aux];
}
return;
}
void query_centro(ll nodo) {
ll aux = centro[nodo], cnt = 0;
if (!h[nodo].empty()) cnt = h[nodo].size()-1;
ans = min(ans,st[nodo]);
while (aux!=0) {
ans = min(ans,st[aux]+h[nodo][cnt]);
cnt--;
aux = centro[aux];
}
return;
}
void Init(int N, int A[], int B[], int D[]) {
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,0,0);
decomp(1,0,0);
for (int i=0;i<=N;i++) st[i] = INF;
return;
}
long long Query(int S, int X[], int T, int Y[]) {
if (S>T) {
swap(S,T);
swap(X,Y);
}
ans = INF;
for (int i=0;i<S;i++) update(X[i]+1);
for (int i=0;i<T;i++) query_centro(Y[i]+1);
for (int i=0;i<S;i++) limpia(X[i]+1);
return ans;
}
/*
int main() {
ios_base::sync_with_stdio(0);cin.tie(0);
int n,q,S,T;
cin>>n>>q;
int A[n-1],B[n-1],D[n-1];
for (int i=0;i<n-1;i++) {
cin>>A[i]>>B[i]>>D[i];
}
Init(n,A,B,D);
while (q--) {
cin>>S>>T;
int X[S],Y[T];
for (int i=0;i<S;i++) cin>>X[i];
for (int i=0;i<T;i++) cin>>Y[i];
cout<<Query(S,X,T,Y)<<'\n';
}
return 0;
}
*/
