#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 5e5 + 2;
const ll LINF = 1e18;
int n, subtree_size[MAXN];
vector<pair<int, ll>> adj[MAXN], ancestors[MAXN];
bitset<MAXN> removed;
ll min_dist_from_source[MAXN];
int dfs_subtree_size(int u, int p, ll depth, int anc) {
subtree_size[u] = 1;
if (anc != -1) ancestors[u].emplace_back(anc, depth);
for (auto v : adj[u]) if (!removed[v.first] && v.first != p)
subtree_size[u] += dfs_subtree_size(v.first, u, depth + v.second, anc);
return subtree_size[u];
}
int find_centroid(int u, int p, int subt_sz) {
for (auto v : adj[u]) if (!removed[v.first] && v.first != p && subtree_size[v.first] > subt_sz / 2)
return find_centroid(v.first, u, subt_sz);
return u;
}
void centroid_decompose(int u) {
int c = find_centroid(u, -1, subtree_size[u]);
removed[c] = 1;
for (auto v : adj[c]) if (!removed[v.first])
dfs_subtree_size(v.first, -1, v.second, c);
for (auto v : adj[c]) if (!removed[v.first])
centroid_decompose(v.first);
}
void Init(int N, int A[], int B[], int D[]) {
n = N;
for (int i = 0; i < n; i++) min_dist_from_source[i] = LINF;
for (int i = 0; i < n - 1; i++) {
adj[A[i]].emplace_back(B[i], D[i]);
adj[B[i]].emplace_back(A[i], D[i]);
}
dfs_subtree_size(0, -1, 0, -1);
centroid_decompose(0);
}
long long Query(int S, int X[], int T, int Y[]) {
ll res = LINF;
for (int i = 0; i < S; i++) {
int u = X[i]; min_dist_from_source[u] = 0;
for (auto v : ancestors[u])
min_dist_from_source[v.first] = min(min_dist_from_source[v.first], v.second);
}
for (int i = 0; i < T; i++) {
int u = Y[i];
res = min(res, min_dist_from_source[u]);
for (auto v : ancestors[u])
res = min(res, min_dist_from_source[v.first] + v.second);
}
for (int i = 0; i < S; i++) {
int u = X[i]; min_dist_from_source[u] = LINF;
for (auto v : ancestors[u])
min_dist_from_source[v.first] = LINF;
}
return res;
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int N, Q; cin >> N >> Q;
int A[N], B[N], D[N];
for (int i = 0; i < N - 1; i++) cin >> A[i] >> B[i] >> D[i];
Init(N, A, B, D);
int S, T;
while (Q--) {
cin >> S >> T;
int X[S], Y[T];
for (int i = 0; i < S; i++) cin >> X[i];
for (int i = 0; i < T; i++) cin >> Y[i];
cout << Query(S, X, T, Y) << '\n';
}
}
Compilation message
/usr/bin/ld: /tmp/ccHKXCzd.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccIImHMc.o:factories.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
