#include <bits/stdc++.h>
#define int long long
using namespace std;
const int Nmax=500010, INF=1e18;
int mx;
int N, Q, sz[Nmax], par[Nmax], lv[Nmax], dep[20][Nmax], num[Nmax];
bool chk[Nmax];
vector<pair<int, int>> adj[Nmax];
int px[Nmax], py[Nmax];
vector<int> X[Nmax], Y[Nmax];
int DFS_S(int curr, int prev) {
sz[curr]=1;
for(auto [next, w]:adj[curr]) if(next!=prev && !chk[next]) sz[curr]+=DFS_S(next, curr);
return sz[curr];
}
int DFS_C(int curr, int prev, int s) {
for(auto [next, w]:adj[curr]) if(next!=prev && !chk[next] && sz[next]>=s/2) return DFS_C(next, curr, s);
return curr;
}
void DFS_D(int curr, int prev, int lev) {
for(auto [next, w]:adj[curr]) if(next!=prev && !chk[next]) {
dep[lev][next]=dep[lev][curr]+w;
DFS_D(next, curr, lev);
}
}
int DnC(int curr, int lev) {
mx=max(mx, lev);
int s=DFS_S(curr, 0), C=DFS_C(curr, 0, s);
chk[C]=true, lv[C]=lev;
DFS_D(C, 0, lev);
for(auto [next, w]:adj[C]) if(!chk[next]) par[DnC(next, lev+1)]=C;
return C;
}
signed main() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin>>N>>Q;
for(int i=1; i<N; i++) {
int u, v, w; cin>>u>>v>>w;
u++, v++;
adj[u].push_back({v, w}), adj[v].push_back({u, w});
}
DnC(1, 0);
fill(num+1, num+N+1, -1);
while(Q--) {
int a, b; cin>>a>>b;
vector<int> V;
for(int i=1; i<=a; i++) {
int x; cin>>x; x++;
for(int p=x; p; p=par[p]) {
X[p].push_back(dep[lv[p]][x]);
if(num[p]!=Q) V.push_back(p), num[p]=Q;
}
}
for(int i=1; i<=b; i++) {
int x; cin>>x; x++;
for(int p=x; p; p=par[p]) {
Y[p].push_back(dep[lv[p]][x]);
if(num[p]!=Q) V.push_back(p), num[p]=Q;
}
}
int ret=INF;
for(int x:V) {
int ma=INF, mb=INF;
for(int i=px[x]; i<X[x].size(); i++) ma=min(ma, X[x][i]);
for(int i=py[x]; i<Y[x].size(); i++) mb=min(mb, Y[x][i]);
ret=min(ret, ma+mb);
px[x]=X[x].size(), py[x]=Y[x].size();
}
cout<<ret<<"\n";
}
return 0;
}
Compilation message
factories.cpp: In function 'int main()':
factories.cpp:70:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
70 | for(int i=px[x]; i<X[x].size(); i++) ma=min(ma, X[x][i]);
| ~^~~~~~~~~~~~
factories.cpp:71:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
71 | for(int i=py[x]; i<Y[x].size(); i++) mb=min(mb, Y[x][i]);
| ~^~~~~~~~~~~~
/usr/bin/ld: /tmp/ccVyiMyg.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cczxJRmh.o:factories.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccVyiMyg.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
