#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#include "factories.h"
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define mkp make_pair
#define in insert
#define er erase
#define fd find
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
typedef long long ll;
typedef long double ld;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll llinf=(1LL<<60);
const int inf=(1<<30);
const int nmax=5e5+50;
const ll mod=1e9+7;
using namespace std;
int n,sz[nmax],tin[nmax],tout[nmax],tt,up[nmax][20],cent[nmax],par[nmax];
ll lvl[nmax],cur[nmax][2];
vector<int>vc;
vector<pair<int,int> >a[nmax];
void dfs_sz(int u,int p)
{
sz[u]=1;
for(int i=0;i<(int)a[u].size();i++)
{
int v=a[u][i].fr;
if(cent[v] || v==p)continue;
dfs_sz(v,u);
sz[u]+=sz[v];
}
}
int dfs_cent(int u,int p,int siz)
{
for(int i=0;i<(int)a[u].size();i++)
{
int v=a[u][i].fr;
if(cent[v] || v==p)continue;
if(sz[v]>siz/2)return dfs_cent(v,u,siz);
}
return u;
}
void decompose(int root,int p=-1)
{
dfs_sz(root,p);
int c=dfs_cent(root,p,sz[root]);
par[c]=p;
cent[c]=1;
for(int i=0;i<(int)a[c].size();i++)
{
int v=a[c][i].fr;
if(cent[v])continue;
decompose(v,c);
}
}
void dfs(int x,int p,int d)
{
tin[x]=++tt;
lvl[x]=lvl[p]+1LL*d;
up[x][0]=p;
for(int i=1;i<19;i++)up[x][i]=up[up[x][i-1]][i-1];
for(int i=0;i<(int)a[x].size();i++)if(a[x][i].fr!=p)dfs(a[x][i].fr,x,a[x][i].sc);
tout[x]=++tt;
}
int anc(int x,int y)
{
return tin[x]<=tin[y] && tout[x]>=tout[y];
}
int lca(int x,int y)
{
if(anc(x,y))return x;
if(anc(y,x))return y;
for(int i=18;i>=0;i--)if(!anc(up[x][i],y))x=up[x][i];
return up[x][0];
}
ll dist(int x,int y)
{
return lvl[x]+lvl[y]-2LL*lvl[lca(x,y)];
}
void Init(int N,int A[],int B[],int D[])
{
n=N;
for(int i=0;i<n-1;i++)
{
A[i]++,B[i]++;
a[A[i]].pb(mkp(B[i],D[i]));
a[B[i]].pb(mkp(A[i],D[i]));
}
dfs(1,1,0);
decompose(1);
for(int i=1;i<=n;i++)cur[i][0]=cur[i][1]=llinf;
}
ll Query(int s,int X[],int t,int Y[])
{
int i,x;
ll rs=llinf;
for(i=0;i<s;i++)
{
x=++X[i];
while(x>=1)
{
cur[x][0]=min(cur[x][0],dist(x,X[i]));
vc.pb(x);
x=par[x];
}
}
for(i=0;i<t;i++)
{
x=++Y[i];
while(x>=1)
{
cur[x][1]=min(cur[x][1],dist(x,Y[i]));
vc.pb(x);
if(cur[x][0]!=llinf)rs=min(rs,cur[x][0]+cur[x][1]);
x=par[x];
}
}
for(i=0;i<(int)vc.size();i++)cur[vc[i]][0]=cur[vc[i]][1]=llinf;
vc.clear();
return rs;
}
/*int main()
{
//freopen("sol.in","r",stdin);
//freopen("sol.out","w",stdout);
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
return 0;
}*/
