#include<bits/stdc++.h>
#include "factories.h"
using namespace std ;
const int LG = 20 , mx = 5e5 + 10 ;
const long long INF = 1e18 ;
set<pair<int,long long> > g[mx] ;
int n , m , p[mx][LG] , depth[mx] , siz[mx] , parent[mx] ;
long long ans[mx] , cost[mx] ;
void dfs(int u , int par , int deep = 0 , long long cst = 0)
{
depth[u] = deep , cost[u] = cst , p[u][0] = par ;
for(pair<int,long long> v : g[u])
{
if(v.first==par) continue ;
dfs(v.first,u,deep+1,cst+v.second) ;
}
}
int comp ;
void visit(int u , int par)
{
++comp , siz[u] = 1;
for(pair<int,long long> v : g[u])
{
if(v.first==par) continue ;
visit(v.first,u) ;
siz[u] += siz[v.first] ;
}
}
int find_centroid(int u , int par)
{
for(pair<int,long long> v : g[u])
{
if(v.first==par) continue ;
if(siz[v.first] > (comp/2))
{
return find_centroid(v.first,u) ;
}
}
return u ;
}
void decompose(int u , int par)
{
comp = 0 , visit(u,u) ;
int centroid = find_centroid(u,u) ;
parent[centroid] = par ;
for(pair<int,long long> v : g[centroid])
{
g[v.first].erase({centroid,v.second}) ;
decompose(v.first,centroid) ;
}
g[centroid].clear() ;
}
int lca(int u , int v)
{
if(depth[u] < depth[v]) swap(u,v) ;
for(int i = LG - 1 ; i >= 0 ; --i)
{
if((depth[u] - (1<<i))>=depth[v]) u = p[u][i] ;
}
if(u==v) return u ;
for(int i = LG - 1 ; i >= 0 ; --i)
{
if(p[u][i] != -1 && p[u][i] != p[v][i])
{
u = p[u][i] , v = p[v][i] ;
}
}
return p[u][0] ;
}
long long dist(int u , int v)
{
return cost[u] + cost[v] - 2*cost[lca(u,v)] ;
}
void update(int u)
{
int x = u ;
while(1)
{
ans[x] = min(ans[x],dist(x,u)) ;
if(parent[x]==x || parent[x] == -1) break ;
x = parent[x] ;
}
}
void clean(int u)
{
int x = u ;
while(1)
{
ans[x] = INF ;
if(parent[x]==x || parent[x] == -1) break ;
x = parent[x] ;
}
}
long long query(int u)
{
int x = u ;
long long res = INF ;
while(1)
{
res = min(res,ans[x] + dist(x,u)) ;
if(parent[x]==x || parent[x] == -1) break ;
x = parent[x] ;
}
return res ;
}
void Init(int N , int A[] , int B[] , int D[])
{
n = N ;
for(int i = 0 ; i < (N-1) ; ++i)
{
g[A[i]].insert({B[i],D[i]}) ;
g[B[i]].insert({A[i],D[i]}) ;
}
memset(p,-1,sizeof(p)) ;
dfs(0,0) ;
decompose(0,-1) ;
for(int j = 1 ; j < LG ; ++j)
{
for(int i = 0 ; i < n ; ++i)
{
if(p[i][j-1] != -1)
{
p[i][j] = p[p[i][j-1]][j-1] ;
}
}
}
for(int i = 0 ; i < n ; ++i) ans[i] = INF ;
}
long long Query(int S , int X[] , int T , int Y[])
{
long long res = INF ;
for(int i = 0 ; i < S ; ++i) update(X[i]) ;
for(int i = 0 ; i < T ; ++i)
{
res = min(res,query(Y[i])) ;
}
for(int i = 0 ; i < S ; ++i) clean(X[i]) ;
return res ;
}
