#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
// void setup()
// {
// #ifndef ONLINE_JUDGE
// freopen("test.inp", "r", stdin);
// freopen("test.out", "w", stdout);
// #endif
// ios_base::sync_with_stdio(0);
// cin.tie(0);
// cout.tie(0);
// }
int ind, x, y, sz[500000], last_centroid[500000], depth[500000], sp[20][1000000], head[500000];
long long dist[500000], nearest[500000], temp;
bool check[500000];
vector<pair<int, int>> g[500000];
void CalculateSize(int node, int par)
{
sz[node] = 1;
for (auto &i : g[node])
{
if (i.first != par && !check[i.first])
{
CalculateSize(i.first, node);
sz[node] += sz[i.first];
}
}
}
int GetCentroid(int node, int par, int root)
{
for (auto &i : g[node])
{
if (i.first != par && !check[i.first] && sz[i.first] * 2 > sz[root])
{
return GetCentroid(i.first, node, root);
}
}
return node;
}
void FindCentroid(int node, int LastCentroid)
{
int centroid;
CalculateSize(node, node);
centroid = GetCentroid(node, node, node);
last_centroid[centroid] = LastCentroid;
check[centroid] = true;
for (auto &i : g[centroid])
{
if (!check[i.first])
{
FindCentroid(i.first, centroid);
}
}
}
void FormLCA(int node, int par)
{
head[node] = ind;
sp[0][ind] = node;
ind++;
for (auto &i : g[node])
{
if (i.first != par)
{
depth[i.first] = depth[node] + 1;
dist[i.first] = dist[node] + i.second;
FormLCA(i.first, node);
sp[0][ind] = node;
ind++;
}
}
}
int LCA(int ina, int inb)
{
int k;
ina = head[ina];
inb = head[inb];
if (ina > inb)
{
swap(ina, inb);
}
k = __lg(inb - ina + 1);
ina = sp[k][ina];
inb = sp[k][inb - (1 << k) + 1];
return (depth[ina] < depth[inb] ? ina : inb);
}
long long Dist(int ina, int inb)
{
return dist[ina] + dist[inb] - 2 * dist[LCA(ina, inb)];
}
void Update(int node)
{
int cur = node;
while (cur != -1)
{
temp = Dist(cur, node);
nearest[cur] = (nearest[cur] == -1 ? temp : min(temp, nearest[cur]));
cur = last_centroid[cur];
}
}
void Reset(int node)
{
int cur = node;
while (cur != -1)
{
nearest[cur] = -1;
cur = last_centroid[cur];
}
}
long long Get(int node)
{
long long res = -1;
int cur = node;
while (cur != -1)
{
if (nearest[cur] != -1)
{
temp = Dist(cur, node) + nearest[cur];
res = (res == -1 ? temp : min(temp, res));
}
cur = last_centroid[cur];
}
return res;
}
long long Query(int S, int X[], int T, int Y[])
{
long long res = 1e18;
for (int i = 0; i < S; ++i)
{
Update(X[i]);
}
for (int i = 0; i < T; ++i)
{
res = min(res, Get(Y[i]));
}
for (int i = 0; i < S; ++i)
{
Reset(X[i]);
}
return res;
}
void Init(int N, int A[], int B[], int D[])
{
fill_n(nearest, N, -1);
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]});
}
depth[0] = dist[0] = ind = 0;
FindCentroid(0, -1);
FormLCA(0, 0);
for (int i = 1; i < 20; ++i)
{
for (int j = 0; j + (1 << i) <= ind; ++j)
{
x = sp[i - 1][j];
y = sp[i - 1][j + (1 << (i - 1))];
sp[i][j] = (depth[x] < depth[y] ? x : y);
}
}
}
// int main()
// {
// setup();
// int n, q, s, t;
// cin >> n >> q;
// int A[n], B[n], D[n];
// for (int i = 0; i < n - 1; ++i)
// {
// cin >> A[i] >> B[i] >> D[i];
// }
// Init(n, A, B, D);
// while (q--)
// {
// cin >> s >> t;
// for (int i = 0; i < s; ++i)
// {
// cin >> A[i];
// }
// for (int i = 0; i < t; ++i)
// {
// cin >> B[i];
// }
// cout << Query(s, A, t, B) << "\n";
// }
// return 0;
// }
