#include <bits/stdc++.h>
using namespace std;
#define sz(v) ((int)((v).size()))
#define all(v) (v).begin(), (v).end()
#define pb push_back
#define coord_comp(v) sort(all(v)), v.erase(unique(all(v)), v.end())
#define v_index(v, x) (lower_bound(all(v),x)-(v).begin())
typedef pair<int,int> pp;
typedef long long ll;
void read(int& x){ scanf("%d",&x); }
void read(ll& x){ scanf("%lld",&x); }
template<typename T1,typename T2>
void read(pair<T1,T2>& p){ read(p.first); read(p.second); }
template<typename T,typename... Args>
void read(T&a,Args&...b){ read(a); read(b...); }
typedef pair<int,ll> pil;
vector<pil> edge[500010];
vector<int> comp[500010];
int par[20][500010];
ll depth[500010];
int d2 [500010];
int n,q;
void in(){
read(n,q);
for(int i=1; i<n; ++i){
int a,b; ll d; read(a,b,d);
edge[a].pb({b,d}); edge[b].pb({a,d});
}
}
int tin[500010];
int nt;
void dfs(int x){
tin[x]=nt++;
for(auto& yp:edge[x]){
int y=yp.first; ll d=yp.second;
if(par[0][x] != y){
par[0][y] = x;
depth[y] = depth[x] + d;
d2[y] = d2[x]+1;
dfs(y);
}
}
}
int lca(int a,int b){
if(d2[a]>d2[b]) swap(a,b);
int df=d2[b]-d2[a];
for(int i=18; 0<=i; --i) if(1&(df>>i)) b=par[i][b];
for(int i=18; 0<=i; --i) if(par[i][a]!=par[i][b])
a=par[i][a], b=par[i][b];
if(a!=b) a=par[0][a];
return a;
}
void sparse(){
par[0][0] = -1;
for(int i=1; i<=18; ++i) for(int j=0; j<n; ++j){
int t=par[i-1][j];
if(t==-1) par[i][j]=-1;
else par[i][j]=par[i-1][t];
}
}
bool isPar(int a,int b){
if(d2[a]>d2[b]) return false;
int df=d2[b]-d2[a];
for(int i=18; 0<=i; --i){
if(1&(df>>i)) b=par[i][b];
}
return a==b;
}
ll dA[500010];
ll dB[500010];
vector<int> hist;
void compress(vector<int>& pts){
stack<int> stk;
hist.clear();
for(int p : pts){
comp[p].clear();
while(stk.size() && !isPar(stk.top(), p))
hist.pb(stk.top()), stk.pop();
if(stk.size()) comp[stk.top()].pb(p);
stk.push(p);
}
while(stk.size()) hist.pb(stk.top()), stk.pop();
}
ll inf=(1LL<<60);
int main(){
in(); dfs(0); sparse();
for(;q--;){
int A, B;
read(A, B);
vector<int> pa(A), pb(B), pts;
for(int i=0; i<A; ++i) read(pa[i]);
for(int i=0; i<B; ++i) read(pb[i]);
for(int x:pa) pts.pb(x);
for(int x:pb) pts.pb(x);
auto timecomp = [&](const int& a, const int& b){
return tin[a]<tin[b];
};
sort(all(pts), timecomp);
int sz=A+B;
for(int i=1; i<sz; ++i) pts.pb(lca(pts[i-1], pts[i]));
sort(all(pts), timecomp);
pts.erase(unique(all(pts)), pts.end());
compress(pts);
for(int x:pts) dA[x]=dB[x]=inf;
for(int x:pa) dA[x]=0;
for(int x:pb) dB[x]=0;
ll ans=inf;
for(int x:hist){
for(int y:comp[x]){
dA[x] = min(dA[x], dA[y]+depth[y]-depth[x]);
dB[x] = min(dB[x], dB[y]+depth[y]-depth[x]);
}
ans=min(ans, dA[x]+dB[x]);
}
printf("%lld\n", ans);
}
return 0;
}
Compilation message
factories.cpp: In function 'void read(int&)':
factories.cpp:10:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
10 | void read(int& x){ scanf("%d",&x); }
| ~~~~~^~~~~~~~~
factories.cpp: In function 'void read(ll&)':
factories.cpp:11:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
11 | void read(ll& x){ scanf("%lld",&x); }
| ~~~~~^~~~~~~~~~~
/tmp/ccXiOKEX.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/cc7yEt2N.o:factories.cpp:(.text.startup+0x0): first defined here
/tmp/ccXiOKEX.o: In function `main':
grader.cpp:(.text.startup+0x317): undefined reference to `Init(int, int*, int*, int*)'
grader.cpp:(.text.startup+0x397): undefined reference to `Query(int, int*, int, int*)'
collect2: error: ld returned 1 exit status
