#include "factories.h"
#include <bits/stdc++.h>
#define all(x) begin(x), end(x)
using namespace std;
using ll = long long;
const char nl = '\n', sp = ' ';
const ll inf = 1e18;
struct centroid_decomposition {
int n;
vector<vector<int> > anc;
vector<vector<ll> > up;
vector<vector<pair<int, int> > > g;
vector<int> sz, colour;
vector<map<ll, int> > closest;
vector<bool> is_removed;
centroid_decomposition() {
}
centroid_decomposition(int n) : n(n) {
g.assign(n, {});
anc.assign(n, {});
closest.assign(n, {});
up.assign(n, {});
sz.assign(n, 0);
colour.assign(n, 0);
is_removed.assign(n, false);
}
void add_edge(int u, int v, int c) {
g[u].emplace_back(v, c);
g[v].emplace_back(u, c);
}
int get_size(int u, int p) {
sz[u] = 1;
for (auto &[v, _]: g[u]) {
if (v == p || is_removed[v]) continue;
sz[u] += get_size(v, u);
}
return sz[u];
}
int get_cent(int u, int p, int m) {
for (auto &[v, _]: g[u]) {
if (v == p || is_removed[v]) continue;
if (sz[v] * 2 > m) return get_cent(v, u, m);
}
return u;
}
void add_node(int u, int p, int centroid, ll weight) {
anc[u].push_back(centroid);
up[u].push_back(weight);
for (auto &[v, c]: g[u]) {
if (v == p || is_removed[v]) continue;
add_node(v, u, centroid, weight + c);
}
}
void decompose(int u = 0) {
int m = get_size(u, -1);
int centroid = get_cent(u, -1, m);
for (auto &[v, c]: g[centroid]) {
if (is_removed[v]) continue;
add_node(v, centroid, centroid, c);
}
is_removed[centroid] = 1;
for (auto &[v, _]: g[centroid]) {
if (is_removed[v]) continue;
decompose(v);
}
reverse(all(anc[centroid]));
reverse(all(up[centroid]));
}
void update(int u) {
if (colour[u]) {
remove(u);
} else {
add(u);
}
colour[u] ^= 1;
}
void add(int u) {
closest[u][0]++;
for (int i = 0; i < anc[u].size(); i++) {
int p = anc[u][i];
ll d = up[u][i];
closest[p][d]++;
}
}
void remove(int u) {
if (--closest[u][0] == 0) closest[u].erase(0);
for (int i = 0; i < anc[u].size(); i++) {
int p = anc[u][i];
ll d = up[u][i];
if (--closest[p][d] == 0) closest[p].erase(d);
}
}
ll query(int u) {
ll ans = closest[u].empty() ? inf : closest[u].begin()->first;
for (int i = 0; i < anc[u].size(); i++) {
int p = anc[u][i];
ll d = up[u][i];
if (closest[p].size()) ans = min(ans, closest[p].begin()->first + d);
}
return ans == inf ? -1 : ans;
}
};
centroid_decomposition cd;
void Init(int N, int A[], int B[], int D[]) {
cd = N;
for (int i = 0; i < N - 1; i++) {
cd.add_edge(A[i], B[i], D[i]);
}
cd.decompose();
}
long long Query(int S, int X[], int T, int Y[]) {
for (int i = 0; i < S; i++) {
cd.update(X[i]);
}
ll ans = inf;
for (int i = 0; i < T; i++) {
ans = min(ans, cd.query(Y[i]));
}
for (int i = 0; i < S; i++) {
cd.update(X[i]);
}
return ans;
}
