#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define pb push_back
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
const ll N = 5e5 + 5, oo = 1e18 + 7, mod = 1e9 + 7;
ll n;
vector<pair<ll, ll>> Adj[N];
ll d1[N], d2[N];
ll anc[N][20];
//dist[N][20];
void dfs(int u, int p){
for(auto it : Adj[u]){
int v = it.fi, w = it.se;
if(v == p) continue;
d1[v] = d1[u] + 1;
d2[v] = d2[u] + w;
anc[v][0] = u;
//dist[v][0] = w;
dfs(v, u);
}
}
void prep(){
for(int i = 1; i <= 19; i++){
for(int j = 1; j <= n; j++){
anc[j][i] = anc[anc[j][i - 1]][i - 1];
//dist[j][i] = dist[j][i - 1] + dist[anc[j][i - 1]][i - 1];
}
}
}
int lca(int x, int y){
if(d1[x] > d1[y]) swap(x, y);
for(int i = 19; i >= 0; i--){
if((d1[x] + (1LL << i)) <= d1[y]) y = anc[y][i];
}
if(x == y) return x;
for(int i = 19; i >= 0; i--){
if(anc[x][i] != anc[y][i]){
x = anc[x][i], y = anc[y][i];
}
}
return anc[x][0];
}
ll dist(int x, int y){
return d2[x] + d2[y] - 2 * d2[lca(x, y)];
}
void Init(int N, vector<int> A, vector<int> B, vector<int> D){
n = N;
for(int i = 0; i < (n - 1); i++){
Adj[A[i] + 1].pb({B[i] + 1, D[i]});
Adj[B[i] + 1].pb({A[i] + 1, D[i]});
}
dfs(1, 1);
prep();
}
ll Query(int S, vector<int> X, int T, vector<int> Y){
if(S <= 5000 && T <= 5000){
ll ans = oo;
for(int i = 0; i < X.size(); i++){
for(int j = 0; j < Y.size(); j++) ans = min(ans, dist(X[i] + 1, Y[j] + 1));
}
return ans;
}
}
void process(){
int n, q;
vector<int> a(n - 1), b(n - 1), d(n - 1);
cin >> n >> q;
for(int i = 0; i < (n - 1); i++){
cin >> a[i] >> b[i] >> d[i];
}
Init(n, a, b, d);
while(q--){
int sz1, sz2;
vector<int> vc1, vc2;
cin >> sz1 >> sz2;
vc1.resize(sz1);
for(int i = 0; i < sz1; i++) cin >> vc1[i];
vc2.resize(sz2);
for(int i = 0; i < sz2; i++) cin >> vc2[i];
cout << Query(sz1, vc1, sz2, vc2) << "\n";
}
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
process();
}
Compilation message
factories.cpp: In function 'long long int Query(int, std::vector<int>, int, std::vector<int>)':
factories.cpp:75:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
75 | for(int i = 0; i < X.size(); i++){
| ~~^~~~~~~~~~
factories.cpp:76:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
76 | for(int j = 0; j < Y.size(); j++) ans = min(ans, dist(X[i] + 1, Y[j] + 1));
| ~~^~~~~~~~~~
factories.cpp:80:1: warning: control reaches end of non-void function [-Wreturn-type]
80 | }
| ^
factories.cpp: In function 'void process()':
factories.cpp:84:21: warning: 'n' is used uninitialized in this function [-Wuninitialized]
84 | vector<int> a(n - 1), b(n - 1), d(n - 1);
| ~~^~~
/usr/bin/ld: /tmp/cc257pWm.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccuiN9bq.o:factories.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/cc257pWm.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
