#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, timer, qIndex, tin[1 + kN], tout[1 + kN], depth[1 + kN], sz[1 + kN], p[1 + kN], curr[1 + kN], lg2[1 + kN], anc[1 + kN][1 + kLog];
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 <= 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) {
tin[u] = ++timer;
for (int i = 1; i <= kLog; ++i) {
anc[u][i] = anc[anc[u][i - 1]][i - 1];
if (anc[u][i] == 0) {
break;
}
}
for (auto it : g[u]) {
int v, w;
tie(v, w) = it;
if (v != anc[u][0]) {
anc[v][0] = u;
depth[v] = depth[u] + 1;
dp[v] = dp[u] + w;
dfs(v);
}
}
tout[u] = timer;
}
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);
}
}
}
bool isAncestor(int u, int v) {
return tin[u] <= tin[v] && tout[v] <= tout[u];
}
int getLca(int u, int v) {
if (depth[u] < depth[v]) {
swap(u, v);
}
if (isAncestor(v, u)) {
return v;
}
for (int i = lg2[depth[v]]; i >= 0; --i) {
if (anc[v][i] && !isAncestor(anc[v][i], u)) {
v = anc[v][i];
}
}
return anc[v][0];
}
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);
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;
}
