#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
const long long inf = (long long)1e18 + 20;
const int ms = 5e5 + 20;
const int st = 22;
vector<pair<int, int>> adj[ms];
long long dt[ms][st];
long long mi[ms];
int de[ms];
int par[ms];
bool f[ms];
int sz[ms];
void dfs1(int u, int pr) {
sz[u] = 1;
for (auto x: adj[u]) {
int v = x.first;
if (v != pr && !f[v]) {
dfs1(v, u);
sz[u] += sz[v];
}
}
}
int ctr(int r, int u, int pr) {
for (auto x: adj[u]) {
int v = x.first;
if (v != pr && !f[v]) {
if (sz[v] * 2 > sz[r]) {
return ctr(r, v, u);
}
}
}
return u;
}
void dfs2(int u, int pr, int d) {
for (auto x: adj[u]) {
int v = x.first;
int w = x.second;
if (v != pr && !f[v]) {
dt[v][d] = dt[u][d] + w;
dfs2(v, u, d);
}
}
}
void build(int u, int pr, int d) {
dfs1(u, -1);
int v = ctr(u, u, -1);
f[v] = true;
de[v] = d;
par[v] = pr;
dt[v][d] = 0;
dfs2(v, -1, d);
for (auto x: adj[v]) {
int w = x.first;
if (!f[w]) {
build(w, v, d + 1);
}
}
}
void Init(int N, int A[], int B[], int D[]) {
for (int i = 1; i <= N; i++) {
mi[i] = inf;
}
for (int i = 0; i < N - 1; i++) {
int u = A[i] + 1;
int v = B[i] + 1;
int w = D[i];
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
build(1, -1, 1);
}
long long Query(int S, int X[], int T, int Y[]) {
for (int i = 0; i < S; i++) {
int u = X[i] + 1;
int d = de[u];
int cc = u;
while (d >= 1) {
mi[cc] = min(mi[cc], dt[u][d]);
cc = par[cc];
d--;
}
}
long long res = inf;
for (int i = 0; i < T; i++) {
int u = Y[i] + 1;
int d = de[u];
int cc = u;
while (d >= 1) {
res = min(res, mi[cc] + dt[u][d]);
cc = par[cc];
d--;
}
}
for (int i = 0; i < S; i++) {
int u = X[i] + 1;
int d = de[u];
int cc = u;
while (d >= 1) {
mi[cc] = inf;
cc = par[cc];
d--;
}
}
return res;
}
