#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
#define MAXN 500005
const long long INF = 1e18;
struct CentroidDecomposition {
vector<int> sub, par;
vector<bool> visited;
vector<vector<int>> adj;
CentroidDecomposition() {}
CentroidDecomposition(int n) : sub(n), par(n), visited(n), adj(n) {}
void addEdge(int u, int v) {
adj[u].push_back(v);
adj[v].push_back(u);
}
void build(int u = 0, int p = -1) {
u = centroid(u, p, dfs(u, p));
par[u] = p;
visited[u] = true;
for (int v : adj[u])
if (!visited[v])
build(v, u);
}
int dfs(int u, int p) {
sub[u] = 1;
for (int v : adj[u])
if (v != p && !visited[v])
sub[u] += dfs(v, u);
return sub[u];
}
int centroid(int u, int p, int sz) {
for (int v : adj[u])
if (v != p && !visited[v] && sub[v] > sz / 2)
return centroid(v, u, sz);
return u;
}
int operator [] (int i) const {
return par[i];
}
};
struct RMQ {
vector<long long> a;
vector<vector<int>> spt;
void init(int n, long long *_a) {
a.resize(n);
spt.assign(1, vector<int>(n));
for (int i=0; i<n; i++) {
a[i] = _a[i];
spt[0][i] = i;
}
for (int j=1; 1<<j<=n; j++) {
spt.emplace_back(n - (1 << j) + 1);
for (int i=0; i+(1<<j)<=n; i++) {
if (a[spt[j-1][i]] < a[spt[j-1][i+(1<<(j-1))]])
spt[j][i] = spt[j-1][i];
else
spt[j][i] = spt[j-1][i+(1<<(j-1))];
}
}
}
int query(int i, int j) {
int k = 31 - __builtin_clz(j - i + 1);
if (a[spt[k][i]] < a[spt[k][j-(1<<k)+1]])
return spt[k][i];
else
return spt[k][j-(1<<k)+1];
}
};
int idx, ti[MAXN], node[2*MAXN];
long long depth[2*MAXN];
vector<pair<int, int>> adj[MAXN];
RMQ rmq;
void dfs(int u, int p, long long d) {
ti[u] = idx;
node[idx] = u;
depth[idx++] = d;
for (auto &e : adj[u])
if (e.first != p) {
dfs(e.first, u, d + e.second);
node[idx] = u;
depth[idx++] = d;
}
}
int lca(int u, int v) {
if (ti[u] > ti[v])
swap(u, v);
return node[rmq.query(ti[u], ti[v])];
}
long long dist(int u, int v) {
return depth[ti[u]] + depth[ti[v]] - 2 * depth[ti[lca(u, v)]];
}
void preprocess() {
idx = 0;
dfs(0, -1, 0);
rmq.init(idx, depth);
}
long long ans[MAXN];
CentroidDecomposition cd;
void Init(int N, int A[], int B[], int D[]) {
cd = CentroidDecomposition(N);
for (int i=0; i<N-1; i++) {
cd.addEdge(A[i], B[i]);
adj[A[i]].emplace_back(B[i], D[i]);
adj[B[i]].emplace_back(A[i], D[i]);
}
cd.build();
preprocess();
for (int i=0; i<N; i++)
ans[i] = INF;
}
long long Query(int S, int X[], int T, int Y[]) {
for (int i=0; i<S; i++) {
int u = X[i];
while (u != -1) {
ans[u] = min(ans[u], dist(X[i], u));
u = cd[u];
}
}
long long ret = INF;
for (int i=0; i<T; i++) {
int u = Y[i];
while (u != -1) {
ret = min(ret, ans[u] + dist(Y[i], u));
u = cd[u];
}
}
for (int i=0; i<S; i++) {
int u = X[i];
while (u != -1) {
ans[u] = INF;
u = cd[u];
}
}
return ret;
}
