#include "factories.h"
#include <vector>
#include <array>
#include <algorithm>
#include <stack>
#include <queue>
using ll = long long;
using namespace std;
int n;
vector<int> tin, tout, h;
vector<vector<pair<int, ll>>> adj;
vector<ll> d;
vector<bool> used;
vector<array<int, 20>> up;
void Init(int n, int A[], int B[], int D[])
{
::n = n;
tin.resize(n);
tout.resize(n);
h.resize(n);
up.resize(n);
d.resize(n, 1e18);
used.resize(n);
::adj.resize(n);
vector<vector<pair<int, ll>>> adj(n);
for (int i = 0; i + 1 < n; ++i)
{
adj[A[i]].emplace_back(B[i], D[i]);
adj[B[i]].emplace_back(A[i], D[i]);
}
int t = 0;
auto dfs = [&t, &adj](auto self, int v, int p) -> void
{
up[v][0] = p;
for (int i = 1; i < 20; ++i) up[v][i] = up[up[v][i - 1]][i - 1];
tin[v] = t++;
for (auto [u, w] : adj[v])
{
if (u != p)
{
h[u] = h[v] + w;
self(self, u, v);
}
}
tout[v] = t - 1;
};
dfs(dfs, 0, 0);
}
bool isParent(int p, int c)
{
return tin[p] <= tin[c] && tout[p] >= tout[c];
}
int lca(int a, int b)
{
if (isParent(a, b)) return a;
if (isParent(b, a)) return b;
for (int i = 19; i >= 0; --i) if (!isParent(up[a][i], b)) a = up[a][i];
return up[a][0];
}
ll dist(int a, int b)
{
return h[a] + h[b] - 2 * h[lca(a, b)];
}
ll Query(int s, int x[], int t, int y[])
{
vector<int> vertices;
for (int i = 0; i < s; ++i) vertices.push_back(x[i]);
for (int i = 0; i < t; ++i) vertices.push_back(y[i]);
sort(vertices.begin(), vertices.end(), [](int a, int b){ return tin[a] < tin[b]; });
int sz = vertices.size();
for (int i = 0; i + 1 < sz; ++i) vertices.push_back(lca(i, i + 1));
sort(vertices.begin(), vertices.end(), [](int a, int b){ return tin[a] < tin[b]; });
vertices.erase(unique(vertices.begin(), vertices.end()), vertices.end());
stack<int> help;
help.push(vertices.front());
for (int i = 1; i < vertices.size(); ++i)
{
while (!isParent(help.top(), vertices[i])) help.pop();
adj[help.top()].emplace_back(vertices[i], dist(help.top(), vertices[i]));
adj[vertices[i]].emplace_back(help.top(), dist(help.top(), vertices[i]));
help.push(vertices[i]);
}
priority_queue<pair<ll, int>> pq;
for (int i = 0; i < s; ++i)
{
pq.push({0, x[i]});
d[x[i]] = 0;
}
while (!pq.empty())
{
auto [ndn, v] = pq.top();
pq.pop();
if (used[v]) continue;
used[v] = true;
for (auto [u, w] : adj[v])
{
if (d[u] > d[v] + w)
{
d[u] = d[v] + w;
pq.push({d[u], u});
}
}
}
ll res = 1e18;
for (int i = 0; i < t; ++i) res = min(res, d[y[i]]);
for (int i : vertices)
{
used[i] = false;
adj[i].clear();
d[i] = 1e18;
}
return res;
}
