#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int ar = 5e5 + 5;
int n, q, N;
int sz[ar], parent[ar];
multiset<ll> se[ar];
vector<int> adj[ar];
bool Deleted[ar];
unordered_map<int, ll> dis[ar];
int vt[ar];
void dfs(int u, int par) {
++N;
sz[u] = 1;
for(auto x : adj[u]) if(x != par && !Deleted[x]) {
dfs(x, u);
sz[u] += sz[x];
}
}
int find_centroid(int u, int par) {
for(auto x : adj[u]) if(x != par && !Deleted[x] && sz[x] > N / 2) return find_centroid(x, u);
return u;
}
void build_distance(int u, int par, int c, ll d) {
dis[c][u] = d;
for(auto x : adj[u]) if(x != par && !Deleted[x]) build_distance(x, u, c, d + dis[u][x]);
}
void build_tree(int u, int par) {
N = 0;
dfs(u, par);
int centroid = find_centroid(u, par);
parent[centroid] = par;
Deleted[centroid] = 1;
build_distance(centroid, par, centroid, 0);
for(int x : adj[centroid]) if(x != parent[centroid] && !Deleted[x]) build_tree(x, centroid);
}
void add(int u) {
for(int par = u; par; par = parent[par]) se[par].insert(dis[par][u]);
}
void del(int u) {
for(int par = u; par; par = parent[par]) se[par].erase(se[par].find(dis[par][u]));
}
ll get(int u) {
ll Min = 1e18;
for(int par = u; par; par = parent[par]) {
if(se[par].size()) Min = min(Min, dis[par][u] + *se[par].begin());
}
return Min;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> q;
for(int i = 1; i < n; ++i) {
int x, y, w; cin >> x >> y >> w;
x++; y++;
adj[x].push_back(y);
adj[y].push_back(x);
dis[x][y] = dis[y][x] = w;
}
build_tree(1, 0);
while(q--) {
int a, b; cin >> a >> b;
for(int i = 1; i <= a; ++i) {
cin >> vt[i];
vt[i]++;
add(vt[i]);
}
ll ans = 1e18;
for(int i = 1; i <= b; ++i) {
int u; cin >> u;
u++;
ans = min(ans, get(u));
}
for(int i = 1; i <= a; ++i) del(vt[i]);
cout << ans << '\n';
}
}
Compilation message
/usr/bin/ld: /tmp/ccdD1GOC.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cc7M7SoC.o:factories.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccdD1GOC.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
