#include <bits/stdc++.h>
#include"factories.h"
using namespace std;
typedef int_fast64_t ll;
const int maxn = 5e5 + 10, maxlog = 19;
ll pai[maxn], h[maxn], block[maxn], sz[maxn], anc[maxn][maxlog], dist[maxn], ans[maxn];
vector<pair<ll, ll>> G[maxn];
vector<ll> tree[maxn], lista;
void dfs(int x, int p)
{
pai[x] = p;
sz[x] = 1;
lista.push_back(x);
for(auto u : G[x])
{
int v = u.first;
if(block[v] or v == p) continue;
dfs(v, x);
sz[x] += sz[v];
}
}
int find_centroid(int x)
{
lista.clear();
dfs(x, x);
int centro = x;
int qt = sz[x];
for(auto u : lista)
{
bool ok = true;
if(qt - sz[u] > qt/2) ok = false;
for(auto v : G[u])
{
int at = v.first;
if(block[at] or pai[u] == at) continue;
if(sz[at] > qt/2) ok = false;
}
if(ok) centro = u;
}
return centro;
}
int build(int x)
{
x = find_centroid(x);
block[x] = true;
for(auto u : G[x])
{
int at = u.first;
if(block[at]) continue;
int v = build(at);
tree[x].push_back(v);
tree[v].push_back(x);
}
return x;
}
void ancestor(int x, int p)
{
h[x] = h[p] + 1;
for(auto v : G[x])
{
int u = v.first;
if(u == p) continue;
anc[u][0] = x;
for(int i = 1; i < maxlog; i++)
anc[u][i] = anc[anc[u][i - 1]][i - 1];
dist[u] = dist[x] + v.second;
ancestor(u, x);
}
}
int lca(int x, int y)
{
if(x == y) return x;
if(h[y] < h[x]) swap(x, y);
for(int i = maxlog - 1; i >= 0 and h[x] != h[y]; i--)
if((h[y] - (1 << i)) >= h[x])
y = anc[y][i];
if(x == y) return x;
for(int i = maxlog - 1; i >= 0; i--)
{
if(anc[y][i] != 0 and anc[x][i] != 0 and anc[x][i] != anc[y][i])
{
x = anc[x][i], y = anc[y][i];
}
}
if(x == y) return x;
return anc[x][0];
}
void init(int x, int p)
{
pai[x] = p;
for(auto u : tree[x])
{
if(u == p) continue;
init(u, x);
}
}
void Init(int N, int A[], int B[], int D[])
{
for(int i = 0; i < N - 1; i++)
{
G[A[i]].push_back({B[i], D[i]});
G[B[i]].push_back({A[i], D[i]});
}
int ct = build(1);
ancestor(ct, ct);
init(ct, -1);
for(int i = 0; i < maxn; i++) ans[i] = (long long)1e17;
}
long long Query(int S, int X[], int T, int Y[])
{
bool ok = false;
if(2*S > T) swap(S, T), ok = true;
for(int i = 0; i < S; i++)
{
int at = X[i];
if(ok) at = Y[i];
int node = at;
while(node != -1)
{
int LCA = lca(node, at);
ans[node] = min(ans[node], dist[node] + dist[at] - 2*dist[LCA]);
node = pai[node];
}
}
ll resp = 1e16;
for(int i = 0; i < T; i++)
{
int at = Y[i];
if(ok) at = X[i];
int node = at;
while(node != -1)
{
int LCA = lca(node, at);
resp = min(resp, ans[node] + dist[node] + dist[at] - 2*dist[LCA]);
node = pai[node];
}
}
for(int i = 0; i < S; i++)
{
int at = X[i];
if(ok) at = Y[i];
int node = at;
while(node != -1)
{
ans[node] = 1e16;
node = pai[node];
}
}
return resp;
}
