#include <bits/stdc++.h>
#ifdef DEBUG
#include <debug.hpp>
#else
#define debug(...) 42
#endif
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
using namespace std;
const ll INF = 1e18;
vector<vector<pair<int, ll>>> gr;
vector<int> sz, used, act;
vector<ll> cls;
vector<vector<int>> cent;
vector<vector<ll>> dist;
int now = 0;
int find_sz(int v, int p) {
sz[v] = 1;
for (auto [to, w] : gr[v]) {
if (used[to] || to == p) continue;
sz[v] += find_sz(to, v);
}
return sz[v];
}
int centr(int v, int p, int cn) {
bool flag = 1;
while (flag) {
flag = 0;
for (auto [to, w] : gr[v]) {
if (used[to] || to == p) continue;
if (sz[to] > cn / 2) {
p = v;
v = to;
flag = 1;
break;
}
}
}
return v;
}
void dfs(int v, int c, int p = -1, ll d = 0) {
cent[v].push_back(c);
dist[v].push_back(d);
assert(cent[v].size() <= 20);
for (auto [to, w] : gr[v]) {
if (used[to] || to == p) continue;
dfs(to, c, v, d + w);
}
}
void Decomp(int v) {
int cn = find_sz(v, v);
int c = centr(v, v, cn);
used[c] = 1;
dfs(c, c);
for (auto [to, w] : gr[c]) {
if (used[to]) continue;
Decomp(to);
}
}
void Init(int N, int A[], int B[], int D[]) {
gr.assign(N, {});
used.assign(N, 0);
sz.assign(N, 0);
cent.assign(N, {});
dist.assign(N, {});
cls.assign(N, INF);
act.assign(N, 0);
for (int i = 0; i < N; ++i) {
gr[A[i]].emplace_back(B[i], D[i]);
gr[B[i]].emplace_back(A[i], D[i]);
}
Decomp(0);
}
void Update(int v) {
for (size_t j = 0; j < cent[v].size(); ++j) {
int c = cent[v][j];
if (act[c] == now) {
cls[c] = min(cls[c], dist[v][j]);
} else {
cls[c] = dist[v][j];
act[c] = now;
}
}
}
ll GetMin(int v) {
ll res = INF;
for (size_t j = 0; j < cent[v].size(); ++j) {
int c = cent[v][j];
if (act[c] == now) {
res = min(res, dist[v][j] + cls[c]);
}
}
return res;
}
ll Query(int S, int X[], int T, int Y[]) {
// go through all X[i] centroids and update cls
for (int i = 0; i < S; ++i) {
Update(X[i]);
}
// go through all Y[i] centroids and update min(res, dist[Y[i]][c] + cls[c])
ll res = INF;
for (int i = 0; i < T; ++i) {
res = min(res, GetMin(Y[i]));
}
// Update actuality
++now;
return res;
}
int main() {
int n, q;
cin >> n >> q;
vector<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.data(), b.data(), d.data());
int s, t;
for (int i = 0; i < q; ++i) {
cin >> s >> t;
vector<int> x(s), y(t);
for (int j = 0; j < s; ++j) {
cin >> x[j];
}
for (int j = 0; j < t; ++j) {
cin >> y[j];
}
cout << Query(s, x.data(), t, y.data()) << "\n";
}
}
Compilation message
/usr/bin/ld: /tmp/cco8LKEG.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccAdmeBG.o:factories.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
