#include<bits/stdc++.h>
// #include"factories.h"
using namespace std;
struct e {
int to;
long long weight;
};
const int dick = 500000 + 5;
vector<e> g[dick];
int nnnn;
int lengthOf[dick];
bool rv[dick];
// first = centroid, second = distance to centroid
vector<pair<int, long long>> DC[dick];
int count(int s, int p = -1) {
lengthOf[s] = 1;
for(auto f : g[s]) {
if(rv[f.to] || f.to == p) continue;
lengthOf[s] += count(f.to, s);
}
return lengthOf[s];
}
int find_centroid(int s, int p = -1, int mn = nnnn) {
for(auto f : g[s]) {
if(rv[f.to] || f.to == p) continue;
if(lengthOf[f.to] * 2 > mn) return find_centroid(f.to, s, mn);
}
return s;
}
long long dist[dick];
void dfs(int s, int p, int C) {
DC[s].push_back({C, dist[s]});
for(auto to : g[s]) {
if(rv[to.to] || to.to == p) continue;
dist[to.to] = dist[s] + to.weight;
dfs(to.to, s, C);
}
}
void decompose(int s) {
int C = find_centroid(s, s, count(s));
dist[C] = 0;
dfs(C, C, C);
rv[C] = 1;
for(auto to : g[C]) {
if(rv[to.to]) continue;
decompose(to.to);
}
}
const long long inf = 1e18;
long long queryDist[dick];
void Init(int N, int A[], int B[], int D[]) {
nnnn = N;
for(int i = 0; i < N - 1; i++) {
g[A[i]].push_back({B[i], D[i]});
g[B[i]].push_back({A[i], D[i]});
}
for(int i = 0; i < N; i++)
queryDist[i] = inf;
decompose(0);
}
long long Query(int S, int X[], int T, int Y[]) {
for(int i = 0; i < T; i++) {
int v = Y[i];
for(auto c : DC[v])
queryDist[c.first] = min(queryDist[c.first], c.second);
}
long long res = 1e18;
for(int i = 0; i < S; i++) {
int v = X[i];
for(auto c : DC[v])
res = min(res, c.second + queryDist[c.first]);
}
for(int i = 0; i < T; i++) {
int v = Y[i];
for(auto c : DC[v])
queryDist[c.first] = inf;
}
return res;
}
// int main() {
// ios::sync_with_stdio(0);
// cin.tie(0);cout.tie(0);
// int n;
// cin >> n;
// int a[n - 1], b[n - 1]; long long d[n - 1];
// for(int i = 0; i < n - 1; i++) {
// cin >> a[i];
// cin >> b[i];
// cin >> d[i];
// }
// Init(n, a, b, d);
// int t;
// cin >> t;
// while(t--) {
// int s, t;
// cin >> s;
// int x[s];
// for(int i = 0; i < s; i++)
// cin >> x[i];
// cin >> t;
// int y[t];
// for(int i = 0; i < t; i++)
// cin >> y[i];
// cout << Query(s, x, t, y) << '\n';
// }
// }
Compilation message
/usr/bin/ld: /tmp/cckuZ72K.o: in function `main':
grader.cpp:(.text.startup+0x181): undefined reference to `countScans(std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status
