#include <bits/stdc++.h>
//#include "factories.h"
#define int long long
using namespace std;
const int maxN = 5e5 + 5, LOG = 20;
const long long INF = (long long) 1e18 + 5;
vector<pair<int, int>> adj[maxN];
int h[maxN], par[LOG][maxN], tin[maxN], tout[maxN], timedfs = 0;
long long w[maxN];
void dfs(int i, int pre){
tin[i] = ++timedfs;
for(pair<int, int> e : adj[i]){
int x = e.first, c = e.second;
if(x == pre) continue;
h[x] = h[i] + 1, w[x] = w[i] + c;
par[0][x] = i;
for(int j = 1; j < LOG; j++) par[j][x] = par[j - 1][par[j - 1][x]];
dfs(x, i);
}
tout[i] = timedfs;
}
int lca(int x, int y){
if(h[x] < h[y]) swap(x, y);
int d = h[x] - h[y];
for(int i = 0; i < LOG; i++){
if(d & (1 << i)) x = par[i][x];
}
if(x == y) return x;
for(int i = LOG - 1; i >= 0; i--){
if(par[i][x] != par[i][y]) x = par[i][x], y = par[i][y];
}
return par[0][x];
}
map<pair<int, int>, long long> mp;
int sz = 0;
int label[maxN];
void Init(int N, int A[], int B[], int D[]){
sz = N;
for(int i = 0; i < N - 1; i++){
adj[A[i]].push_back({B[i], D[i]});
adj[B[i]].push_back({A[i], D[i]});
}
dfs(0, 0);
memset(label, -1, sizeof label);
}
vector<pair<int, int>> adj2[maxN];
bool in(int x, int y){
return tin[x] <= tin[y] && tin[y] <= tout[x];
}
int dp[2][maxN], ans;
void dfs2(int i){
for(pair<int, int> e : adj2[i]){
int x = e.first, w = e.second;
dfs2(x);
dp[0][i] = min(dp[0][i], dp[0][x] + w);
dp[1][i] = min(dp[1][i], dp[1][x] + w);
}
if(label[i] != -1){
ans = min(ans, dp[label[i] ^ 1][i]);
}
dp[label[i]][i] = 0;
ans = min(ans, dp[0][i] + dp[1][i]);
}
long long Query(int S, int X[], int T, int Y[]){
vector<int> v; ans = INF;
for(int i = 0; i < S; i++) v.push_back(X[i]), label[X[i]] = 0;
for(int i = 0; i < T; i++) v.push_back(Y[i]), label[Y[i]] = 1;
sort(v.begin(), v.end(), [](int x, int y){return tin[x] < tin[y];});
for(int i = v.size() - 2; i >= 0; i--){
v.push_back(lca(v[i], v[i + 1]));
}
sort(v.begin(), v.end(), [](int x, int y){return tin[x] < tin[y];});
v.resize(unique(v.begin(), v.end()) - v.begin());
stack<int> st; st.push(v[0]);
for(int i = 1; i < v.size(); i++){
while(st.size() && !in(st.top(), v[i])) st.pop();
adj2[st.top()].push_back({v[i], w[v[i]] - w[st.top()]});
st.push(v[i]);
}
for(int x : v) dp[0][x] = dp[1][x] = INF;
dfs2(v[0]);
for(int x : v) label[x] = -1;
for(int x : v) adj2[x].clear();
while(st.size()) st.pop();
return ans;
}
#ifdef LOCAL
const int MAX = 1e3 + 5;
signed main(){
ios_base::sync_with_stdio(0); cin.tie(0);
int n, q; cin >> n >> q;
int x[MAX], y[MAX], d[MAX];
for(int i = 0; i < n - 1; i++){
cin >> x[i] >> y[i] >> d[i];
}
Init(n, x, y, d);
for(int i = 1; i <= q; i++){
int s, t; cin >> s >> t;
int a[MAX], b[MAX];
for(int i = 0; i < s; i++) cin >> a[i];
for(int i = 0; i < t; i++) cin >> b[i];
cout << Query(s, a, t, b) << '\n';
}
return 0;
}
#endif
Compilation message
factories.cpp: In function 'long long int Query(long long int, long long int*, long long int, long long int*)':
factories.cpp:85:22: 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]
85 | for(int i = 1; i < v.size(); i++){
| ~~^~~~~~~~~~
/usr/bin/ld: /tmp/ccDJxCMv.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
