#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define cmin(a, b) a = min(a, b)
const int inf = 1e18;
const signed LOG=18;
signed n;
vector<pair<signed, signed>> adj[500005];
pair<signed, int> up[500005][LOG];
signed depth[500005];
unordered_map<signed, unordered_map<signed, int>> dists;
void dfsinit(signed u, signed p) {
for (auto [v, w]: adj[u]) if (v!=p) {
up[v][0]={u, w};
for (int i=1; i<LOG; i++) {
if (up[v][i-1].fi==-1) break;
up[v][i]=up[up[v][i-1].fi][i-1];
up[v][i].se+=up[v][i-1].se;
}
depth[v]=depth[u]+1;
dfsinit(v, u);
}
}
int dist(signed a, signed b) {
if (a==b) return 0;
if (dists[a].count(b)) return dists[a][b];
int basea=a, baseb=b;
if (depth[a]<depth[b]) swap(a, b);
int ans=0;
signed k=depth[a]-depth[b];
for (signed i=0; i<LOG&&k; i++) {
if (k&(1<<i)) ans+=up[a][i].se, a=up[a][i].fi, k^=1<<i;
}
if (a==b) return dists[basea][baseb]=ans;
for (signed i=LOG-1; i>=0; i--) if (up[a][i].fi!=up[b][i].fi) {
ans+=up[a][i].se+up[b][i].se;
a=up[a][i].fi, b=up[b][i].fi;
}
return dists[basea][baseb]=ans+up[a][0].se+up[b][0].se;
}
signed sz[500005], par[500005];
bool centro[500005];
void dfs(signed u, signed p) {
sz[u]=1;
for (auto [v, w]: adj[u]) if (v!=p && !centro[v]) {
dfs(v, u);
sz[u]+=sz[v];
}
}
signed centroid(signed u, signed p, signed obj) {
for (auto [v, w]: adj[u]) if (v!=p && !centro[v]) {
if (sz[v]*2>=obj) return centroid(v, u, obj);
}
return u;
}
signed decompose(signed u, signed p) {
if (centro[u]) return u;
dfs(u, u);
signed c=centroid(u, u, sz[u]); centro[c]=1;
par[c]=p;
for (auto [v, w]: adj[c]) if (!centro[v]) {
decompose(v, c);
}
return c;
}
int distres[500005];
void update(signed u, signed changing) {
if (u==-1) return;
cmin(distres[u], dist(u, changing));
update(par[u], changing);
}
void reset(signed u, signed changing) {
if (u==-1) return;
distres[u]=inf;
reset(par[u], changing);
}
int query(signed u, signed changing) {
if (u==-1) return inf;
return min(distres[u]+dist(u, changing), query(par[u], changing));
}
void Init(signed N, signed A[], signed B[], signed D[]) {
n=N;
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]});
distres[i]=inf, centro[i]=0;
}
distres[n-1]=inf, centro[n-1]=0;
dfsinit(0, 0);
decompose(0, -1);
}
int Query(signed S, signed X[], signed T, signed Y[]) {
int ans=inf;
for (int i=0; i<S; i++) update(X[i], X[i]);
for (int i=0; i<T; i++) cmin(ans, query(Y[i], Y[i]));
for (int i=0; i<S; i++) reset(X[i], X[i]);
return ans;
}
