#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
const int kN = 5e5;
const int kLog = 18;
const int64_t INF = 1e18L;
int N, M, qIndex, tin[1 + kN], tout[1 + kN], tour[1 + kN], depth[1 + kN], sz[1 + kN], p[1 + kN], curr[1 + kN], lg2[2 * kN], rmq[2 * kN][1 + kLog + 1];
int64_t dp[1 + kN], best[1 + kN];
vector<pair<int, int>> g[1 + kN];
bitset<1 + kN> vis;
vector<int> modified;
void precalc() {
for (int i = 2; i < 2 * kN; ++i) {
lg2[i] = lg2[i / 2] + 1;
}
}
void minSelf(int64_t &x, int64_t y) {
if (y < x) {
x = y;
}
}
void dfs(int u, int par) {
depth[u] = depth[par] + 1;
tin[u] = ++M;
tour[M] = u;
for (auto it : g[u]) {
int v, w;
tie(v, w) = it;
if (v != par) {
dp[v] = dp[u] + w;
dfs(v, u);
tour[++M] = u;
}
}
tout[u] = ++M;
tour[M] = u;
}
void buildRmq() {
for (int i = 1; i <= M; ++i) {
rmq[i][0] = tour[i];
}
for (int j = 1; (1 << j) <= M; ++j) {
for (int i = 1; i + (1 << j) - 1 <= M; ++i) {
rmq[i][j] = rmq[i][j - 1];
if (depth[rmq[i + (1 << (j - 1))][j - 1]] < depth[rmq[i][j]]) {
rmq[i][j] = rmq[i + (1 << (j - 1))][j - 1];
}
}
}
}
void findSize(int u, int par) {
sz[u] = 1;
for (auto it : g[u]) {
int v = it.first;
if (!vis[v] && v != par) {
findSize(v, u);
sz[u] += sz[v];
}
}
}
int findCentroid(int u, int par) {
for (auto it : g[u]) {
int v = it.first;
if (!vis[v] && v != par && sz[v] > N / 2) {
return findCentroid(v, u);
}
}
return u;
}
void build(int u, int par) {
findSize(u, 0);
int c = findCentroid(u, 0);
vis[c] = true;
p[c] = par;
for (auto it : g[c]) {
int v = it.first;
if (!vis[v]) {
build(v, c);
}
}
}
int getLca(int u, int v) {
if (tin[v] < tin[u]) {
swap(u, v);
}
int diff = tin[v] - tin[u] + 1;
int k = lg2[diff];
int shift = diff - (1 << k);
if (depth[rmq[tin[u]][k]] < depth[rmq[tin[u] + shift][k]]) {
return rmq[tin[u]][k];
}
return rmq[tin[u] + shift][k];
}
int64_t getDist(int u, int v, int lca) {
return dp[u] + dp[v] - 2 * dp[lca];
}
void update(int u) {
best[u] = 0;
int v = u;
while (v) {
if (curr[v] != qIndex) {
curr[v] = qIndex;
modified.emplace_back(v);
}
minSelf(best[v], getDist(u, v, getLca(u, v)));
v = p[v];
}
}
int64_t query(int u) {
int64_t ans = INF;
int v = u;
while (v) {
minSelf(ans, best[v] + getDist(u, v, getLca(u, v)));
v = p[v];
}
return ans;
}
void Init(int n, int a[], int b[], int d[]) {
N = n;
precalc();
for (int i = 0; i <= n - 2; ++i) {
a[i] += 1;
b[i] += 1;
g[a[i]].emplace_back(b[i], d[i]);
g[b[i]].emplace_back(a[i], d[i]);
}
dfs(1, 0);
buildRmq();
build(1, 0);
for (int v = 1; v <= n; ++v) {
best[v] = INF;
}
}
long long Query(int n, int x[], int m, int y[]) {
qIndex += 1;
modified.clear();
for (int i = 0; i < n; ++i) {
x[i] += 1;
update(x[i]);
}
int64_t ans = INF;
for (int i = 0; i < m; ++i) {
y[i] += 1;
minSelf(ans, query(y[i]));
}
for (int v : modified) {
best[v] = INF;
}
return ans;
}
