#include <bits/stdc++.h>
#include"factories.h"
using namespace std;
typedef int_fast64_t ll;
#pragma GCC optimize ("Ofast")
const int maxn = 5e5 + 10, maxlog = 19;
int pai[maxn], h[maxn], block[maxn], last[maxn];
ll ans[maxn], dist[maxn][maxlog];
vector<pair<int, int>> G[maxn];
vector<int> tree[maxn], lista;
void find_dist(int v, int p, ll depht)
{
dist[v][h[v]++] = depht;
for(auto u : G[v])
{
if(u.first == p or block[u.first]) continue;
find_dist(u.first, v, depht + u.second);
}
}
using ii = pair<int, int>;
const int inf = 0x3f3f3f3f;
int n, k;
vector<int> v[maxn];
int sz[maxn];
int cvis[maxn];
int tam(int x, int p)
{
sz[x] = 1;
for (int u : v[x]) {
if (cvis[u] or u == p) continue;
sz[x] += tam(u, x);
}
return sz[x];
}
int tot;
ii best;
void split(int x, int p)
{
int heav = tot - sz[x];
for (int u : v[x]) {
if (cvis[u] or u == p) continue;
heav = max(heav, sz[u]);
split(u, x);
}
if (best.second > heav) best = {x, heav};
}
int centroid(int x)
{
tot = tam(x, x);
best = {0, inf};
split(x, x);
find_dist(x, x, 0);
return best.first;
}
int solve(int x)
{
int cent = centroid(x);
cvis[cent] = 1;
for (int u : v[cent]) {
if (cvis[u]) continue;
int p = solve(u);
tree[cent].push_back(p);
tree[p].push_back(cent);
}
return cent;
}
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 = solve(1);
init(ct, -1);
for(int i = 0; i < maxn; i++) ans[i] = (long long)1e17;
}
int it;
long long Query(int S, int X[], int T, int Y[])
{
it++;
for(int i = 0; i < S; i++)
{
int v = X[i];
int x = v;
for(int j = h[x] - 1; j >= 0; j--)
{
if(last[v] != it)
{
last[v] = it;
ans[v] = dist[x][j];
}
else ans[v] = min(ans[v], dist[x][j]);
v = pai[v];
}
}
ll resp = 1e16;
for(int i = 0; i < T; i++)
{
int v = Y[i];
int x = v;
for(int j = h[x] - 1; j >= 0; j--)
{
if(last[v] == it) resp = min(resp, ans[v] + dist[x][j]);
v = pai[v];
}
}
return resp;
}
