#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
#define mkp make_pair
const int MAXN = 5 * 100100, MAXLN = 20;
const long long LINF = 0x3f3f3f3f3f3f3f3f;
int n, sz[MAXN], cdp[MAXN], memo[MAXN][MAXLN], lvl[MAXN];
long long distrt[MAXN], aux[MAXN];
bool rmd[MAXN];
vector<pair<int, int>> g[MAXN];
void szdfs(int v, int p = -1)
{
sz[v] = 1;
for(const auto&[w, u] : g[v])
if(u != p && !rmd[u])
szdfs(u, v), sz[v] += sz[u];
}
int getCentroid(int v, int p = -1, int rt = -1)
{
if(rt == -1)
rt = v;
for(const auto&[w, u] : g[v])
if(u != p && !rmd[u] && sz[u] > sz[rt] / 2)
return getCentroid(u, v, rt);
return v;
}
void cd(int v, int cp = -1)
{
szdfs(v);
int c = getCentroid(v);
cdp[c] = cp, rmd[c] = true;
for(const auto&[w, u] : g[c])
if(!rmd[u])
cd(u, c);
}
void lcadfs(int v, int p = -1)
{
for(const auto&[w, u] : g[v])
if(u != p)
lvl[u] = lvl[v] + 1, memo[u][0] = v, distrt[u] = distrt[v] + w, lcadfs(u, v);
}
int dp(int v, int i)
{
if(memo[v][i] != -1)
return memo[v][i];
return memo[v][i] = dp(dp(v, i - 1), i - 1);
}
int lca(int u, int v)
{
if(lvl[u] < lvl[v])
swap(u, v);
for(int i = MAXLN - 1; i >= 0; --i)
if(lvl[u] - (1 << i) >= lvl[v])
u = dp(u, i);
if(u == v)
return u;
for(int i = MAXLN - 1; i >= 0; --i)
if(lvl[u] - (1 << i) >= 0 && dp(u, i) != dp(v, i))
u = dp(u, i), v = dp(v, i);
return dp(u, 0);
}
long long getdist(int u, int v)
{
return distrt[u] + distrt[v] - 2 * distrt[lca(u, v)];
}
void Init(int N, int A[], int B[], int D[])
{
memset(memo, -1, sizeof memo);
n = N;
for(int i = 0; i < n - 1; ++i)
g[A[i]].push_back(mkp(D[i], B[i])), g[B[i]].push_back(mkp(D[i], A[i]));
cd(0), lcadfs(0);
}
long long Query(int S, int X[], int T, int Y[])
{
long long ans = LINF;
memset(aux, (int)LINF, sizeof aux);
for(int i = 0, cur; i < S; ++i)
{
cur = X[i];
while(cur != -1)
{
aux[cur] = min(aux[cur], getdist(cur, X[i]));
cur = cdp[cur];
}
}
for(int i = 0, cur; i < T; ++i)
{
cur = Y[i];
while(cur != -1)
{
ans = min(ans, aux[cur] + getdist(Y[i], cur));
cur = cdp[cur];
}
}
return ans;
}
