#include "factories.h"
#include <bits/stdc++.h>
#define int long long
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
using namespace std;
vector<vector<pair<int,int>>> neigh;
vector<pair<int,int>> parent;
vector<vector<int>> parent2;
vector<int> childC;
vector<int> cindx;
vector<int> depth;
vector<int> depthD;
vector<int> ans;
int n;
int K;
int ct=0;
int _n=0;
int solu=1e18;
const int LOG=18;
int build_tree(int x, int p){
childC[x]=1;
for (int t=0; t<sz(neigh[x]); t++)
{
int u=neigh[x][t].first;
if(u==p||cindx[u]>=0) continue;
childC[x]+=build_tree(u,x);
}
return childC[x];
}
pair<int,int> centroid(int x, int p){
for (int t=0; t<sz(neigh[x]); t++)
{
int u=neigh[x][t].first;
if(u==p||cindx[u]>=0) continue;
if(childC[u]*2>=_n) {
pair<int,int> c=centroid(u,x);
return {c.first,c.second+neigh[x][t].second};
}
}
return {x,0};
}
pair<int,int> decompo(int x, int compoINDEX){
build_tree(x,-1);
_n=childC[x];
pair<int,int> c=centroid(x,-1);
cindx[c.first]=compoINDEX;
for (auto u : neigh[c.first])
{
if(cindx[u.first]>=0) continue;
pair<int,int> dc=decompo(u.first,compoINDEX+1);
parent[dc.first]={c.first,dc.second+u.second};
}
return c;
}
void build_lca(int x, int p, int dp, int dp2){
depth[x]=dp;
depthD[x]=dp2;
for (int t=0; t<sz(neigh[x]); t++)
{
int u=neigh[x][t].first;
if(u==p) continue;
build_lca(u,x,dp+1,dp2+neigh[x][t].second);
parent2[u][0]=x;
}
return;
}
void lca_prep(){
for (int j = 1; j < LOG; j++)
{
for (int i = 0; i < n; i++)
{
parent2[i][j]=parent2[parent2[i][j-1]][j-1];
}
}
}
int lca(int a, int b){
if(depth[b]<depth[a]) swap(a,b);
int d=depth[b]-depth[a];
for (int j = LOG-1; j >= 0;j--)
{
if(d&(1<<j)) b=parent2[b][j];
}
if(a==b) return a;
for (int j = LOG-1; j >= 0;j--)
{
if(parent2[a][j]!=parent2[b][j]) {
a=parent2[a][j];
b=parent2[b][j];
}
}
return parent2[a][0];
}
int dist(int a, int b){
return depthD[a]+depthD[b]-2*depthD[lca(a,b)];
}
void update(int x, int obj){
ans[x]=min(ans[x],dist(x,obj));
if(parent[x].first==-1) return;
update(parent[x].first, obj);
}
int query(int x, int obj){
if(parent[x].first==-1) return ans[x]+dist(x,obj);
return min(ans[x]+dist(x,obj),query(parent[x].first,obj));
}
void clear(int x){
ans[x]=1e18;
if(parent[x].first==-1) return;
clear(parent[x].first);
}
void Init(signed N, signed A[], signed B[], signed D[]) {
n=N;
neigh.resize(n);
cindx.resize(n);
childC.resize(n,0);
depth.resize(n,0);
depthD.resize(n,0);
parent.resize(n,{-1,-1});
parent2.resize(n,vector<int>(LOG,0));
ans.resize(n,1e18);
for (int i = 0; i < n-1; i++)
{
int a=A[i],b=B[i];
neigh[a].push_back({b,D[i]});
neigh[b].push_back({a,D[i]});
}
cindx.clear(); cindx.resize(n,-1);
childC.resize(n);
build_lca(0,-1,0,0);
parent2[0][0]=0;
lca_prep();
decompo(0,0);
}
long long Query(signed S, signed X[], signed T, signed Y[]) {
if(S>T){
swap(S,T);
swap(X,Y);
}
int mn=1e18;
for (int i = 0; i < S; i++)
{
update(X[i],X[i]);
}
for (int i = 0; i < T; i++)
{
mn=min(mn,query(Y[i],Y[i]));
}
for (int i = 0; i < S; i++)
{
clear(X[i]);
}
return mn;
}
