#include <bits/stdc++.h>
#define int long long
const int maxn = 5e5 + 5;
const int LG = 19;
const int INF = 1e17;
int n, q, timeDfs;
int sparse[maxn + 5][LG + 5], par[maxn + 5];
int d[maxn + 5], lg[maxn + 5], sz[maxn + 5], depth[maxn + 5], h[maxn + 5], tin[maxn + 5];
bool del[maxn + 5];
std::vector<std::pair<int, int>> g[maxn + 5];
void init() {
for (int i = 2; i <= maxn; ++i)
lg[i] = lg[i / 2] + 1;
}
int combine(int u, int v) {
return h[u] < h[v] ? u : v;
}
void dfs(int u, int p) {
sparse[++timeDfs][0] = u;
tin[u] = timeDfs;
for (std::pair<int, int> tmp : g[u]) {
int v = tmp.first;
int w = tmp.second;
if (v == p) continue;
depth[v] = depth[u] + w;
h[v] = h[u] + 1;
dfs(v, u);
sparse[++timeDfs][0] = u;
}
}
int find_centroid(int u, int p, int m) {
for (std::pair<int, int> tmp : g[u]) {
int v = tmp.first;
if (del[v] || v == p) continue;
if (sz[v] > m / 2) return find_centroid(v, u, m);
}
return u;
}
void reset_sz(int u, int p) {
sz[u] = 1;
for (std::pair<int, int> tmp : g[u]) {
int v = tmp.first;
if (del[v] || v == p) continue;
reset_sz(v, u);
sz[u] += sz[v];
}
}
int dist(int u, int v) {
if (tin[u] > tin[v]) std::swap(u, v);
int base = lg[tin[v] - tin[u] + 1];
int lca = combine(sparse[tin[u]][base], sparse[tin[v] - (1 << base) + 1][base]);
return depth[u] + depth[v] - 2 * depth[lca];
}
int CD(int u) {
reset_sz(u, 0);
int cen = find_centroid(u, 0, sz[u]);
del[cen] = true;
for (std::pair<int, int> tmp : g[cen]) {
int v = tmp.first;
if (del[v]) continue;
par[CD(v)] = cen;
}
return cen;
}
void update(int u) {
int anc = u;
while (anc) {
d[anc] = std::min(d[anc], dist(u, anc));
anc = par[anc];
}
}
int query(int u) {
int anc = u;
int ans = INF;
while (anc) {
ans = std::min(ans, dist(u, anc) + d[anc]);
anc = par[anc];
}
return ans;
}
void init_d(int u) {
int anc = u;
while (anc) {
d[anc] = INF;
anc = par[anc];
}
}
void solve() {
std::cin >> n >> q;
for (int i = 1, u, v, w; i < n; ++i) {
std::cin >> u >> v >> w;
g[u].push_back({v, w});
g[v].push_back({u, w});
}
dfs(1, 0);
for (int j = 1; j <= LG; ++j) {
for (int i = 1; i <= timeDfs; ++i) {
sparse[i][j] = combine(sparse[i][j - 1], sparse[i + (1 << (j - 1))][j - 1]);
}
}
CD(1);
for (int i = 1; i <= n; ++i) d[i] = INF;
std::vector<int> nd;
for (int _ = 1; _ <= q; ++_) {
int sn, sm; std::cin >> sn >> sm;
for (int i = 1; i <= sn; ++i) {
int u; std::cin >> u;
nd.push_back(u);
update(u);
}
int ans = INF;
for (int i = 1; i <= sm; ++i) {
int u; std::cin >> u;
ans = std::min(ans, query(u));
}
std::cout << ans << '\n';
for (int u : nd)
init_d(u);
nd.clear();
}
}
signed main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(0);
int tc = 1;
// std::cin >> tc;
init();
while (tc--) {
solve();
}
}
Compilation message
/usr/bin/ld: /tmp/ccwzZw1B.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccCik2bC.o:factories.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccwzZw1B.o: in function `main':
grader.cpp:(.text.startup+0x37d): undefined reference to `Init(int, int*, int*, int*)'
/usr/bin/ld: grader.cpp:(.text.startup+0x412): undefined reference to `Query(int, int*, int, int*)'
collect2: error: ld returned 1 exit status
