#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
const int LOGN = 20;
vector<pair<int, int>> g[maxn];
ll best[maxn];
int sz[maxn], pi[maxn];
bool block[maxn];
int n;
int st[maxn], fin[maxn], timer = 0;
int up[maxn][LOGN];
ll h[maxn];
void dfs(int v, int p) {
st[v] = timer++;
up[v][0] = p;
for(int i = 1; i < LOGN; i++)
up[v][i] = up[up[v][i-1]][i-1];
for(auto [to, d] : g[v]) if(to != p) {
h[to] = h[v] + d;
dfs(to, v);
}
fin[v] = timer++;
}
bool is_parent(int u, int v) { return st[u] <= st[v] and fin[v] <= fin[u]; }
int lca(int u, int v) {
if(is_parent(u, v)) return u;
if(is_parent(v, u)) return v;
for(int i = LOGN-1; i >= 0; i--) {
if(!is_parent(up[u][i], v)) {
u = up[u][i];
}
}
return up[u][0];
}
ll dist(int u, int v) {
int p = lca(u, v);
return h[u] + h[v] - 2 * h[p];
}
int centroid(int v, int p, int n) {
sz[v] = 1;
int mx=0, cen=0;
for (auto [u, d] : g[v]) if (u!=p && !block[u]) {
cen ^= centroid(u, v, n);
sz[v] += sz[u], mx=max(mx, sz[u]);
}
mx = max(mx, n-sz[v]);
if (2*mx <= n) pi[cen=v]=p;
return cen;
}
void decompose(int x, int p=-1, int m=n) {
int cen = centroid(x, -1, m);
if (~pi[cen]) sz[pi[cen]]=m-sz[cen];
pi[cen]=p; block[cen]=1;
for (auto [v, d] : g[cen]) if (!block[v]) {
decompose(v, cen, sz[v]);
}
}
const ll INF = (ll) 2e18;
void update(int v, ll d=0) {
best[v] = d;
if(pi[v] != -1) update(pi[v], d + dist(v, pi[v]));
}
void clean(int v) {
best[v] = INF;
if(pi[v] != -1) clean(pi[v]);
}
ll query(int v) {
ll ans = INF;
int u = v;
do {
ans = min(ans, dist(u, v) + best[u]);
u = pi[u];
} while(u != -1);
return ans;
}
int main() {
int q; cin >> n >> q;
for(int i = 0; i < n-1; i++) {
int u, v, d; cin >> u >> v >> d;
g[u].push_back({v, d});
g[v].push_back({u, d});
}
for(int i = 0; i < n; i++) {
best[i] = INF;
}
decompose(0);
dfs(0, 0);
for(int i = 0; i < q; i++) {
int s, t; cin >> s >> t;
vector<int> sv;
for(int j = 0; j < s; j++) {
int u; cin >> u;
update(u);
sv.push_back(u);
}
ll ans = INF;
for(int j = 0; j < t; j++) {
int u; cin >> u;
ans = min(ans, query(u));
}
for(int x : sv) clean(x);
cout << ans << "\n";
}
return 0;
}
Compilation message
/usr/bin/ld: /tmp/cc5u8kM6.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cccdoQI8.o:factories.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/cc5u8kM6.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
