#include <bits/stdc++.h>
#include "factories.h"
#define ff first
#define ss second
using namespace std;
const int maxn = 5e5+10;
const long long inf = 1e18+10;
typedef pair<int, int> pii;
typedef long long ll;
int n;
int tab[maxn][20], nivel[maxn];
int sz[maxn], pai[maxn];
int x[maxn], y[maxn];
ll dist[maxn], child[maxn];
bool mark[maxn];
vector<pii> grafo[maxn];
void dfs(int u, int p)
{
for (auto pp: grafo[u])
{
int v = pp.ff, d = pp.ss;
if (v == p) continue;
tab[v][0] = u, nivel[v] = nivel[u]+1;
dist[v] = dist[u]+(ll)d;
dfs(v, u);
}
}
int dfs2(int u, int p)
{
sz[u] = 1;
for (auto pp: grafo[u])
{
int v = pp.ff;
if (v == p || mark[v]) continue;
sz[u] += dfs2(v, u);
}
return sz[u];
}
int centroid(int S, int u, int p)
{
for (auto pp: grafo[u])
{
int v = pp.ff;
if (v == p || mark[v]) continue;
if (sz[v] > S/2) return centroid(S, v, u);
}
return u;
}
int decompose(int u)
{
dfs2(u, -1);
int c = centroid(sz[u], u, -1);
mark[c] = 1;
for (auto pp: grafo[c])
{
int v = pp.ff;
if (mark[v]) continue;
int c2 = decompose(v);
pai[c2] = c;
}
return c;
}
int lca(int u, int v)
{
if (nivel[u] < nivel[v]) swap(u, v);
for (int i = 19; i >= 0; i--)
if (nivel[u]-(1<<i) >= nivel[v])
u = tab[u][i];
if (u == v) return u;
for (int i = 19; i >= 0; i--)
if (tab[u][i] && tab[v][i] && tab[u][i] != tab[v][i])
u = tab[u][i], v = tab[v][i];
return tab[u][0];
}
void Init(int N, int A[], int B[], int D[])
{
n = N;
for (int i = 0; i < n-1; i++)
{
grafo[A[i]].push_back({B[i], D[i]});
grafo[B[i]].push_back({A[i], D[i]});
}
memset(pai, -1, sizeof pai);
memset(tab, -1, sizeof tab);
for (int i = 0; i < n; i++)
child[i] = inf;
dfs(0, -1);
decompose(0);
for (int j = 1; j < 20; j++)
for (int i = 0; i < n; i++)
if (tab[i][j-1] != -1)
tab[i][j] = tab[tab[i][j-1]][j-1];
}
long long Query(int S, int X[], int T, int Y[])
{
int s = S, t = T;
for (int i = 0; i < s; i++)
x[i] = X[i];
for (int i = 0; i < t; i++)
y[i] = Y[i];
vector<int> vis;
for (int i = 0; i < t; i++)
{
int v = y[i];
while (v != -1)
{
vis.push_back(v);
ll d = dist[y[i]]+dist[v]-2LL*dist[lca(y[i], v)];
child[v] = min(child[v], d);
v = pai[v];
}
}
ll ans = inf;
for (int i = 0; i < s; i++)
{
int v = x[i];
while (v != -1)
{
ll d = dist[x[i]]+dist[v]-2LL*dist[lca(x[i], v)];
ans = min(ans, d+child[v]);
v = pai[v];
}
}
for (auto x: vis) child[x] = inf;
return ans;
}
