#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <array>
#include <iomanip>
#include <queue>
#include <stack>
#include <numeric>
#include <cassert>
#include <cmath>
#include <random>
#include <ctime>
#include <chrono>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)x.size())
#define rep(i, a, b) for(int i = a; i < b; ++i)
template <typename T>
void remove_duplicates(vector<T> &v){
sort(all(v));
v.resize(unique(all(v)) - v.begin());
}
template <typename T> void chmin(T &a, T b){ a = (b < a) ? b : a; }
template <typename T> void chmax(T &a, T b){ a = (b > a) ? b : a; }
template<class T>
struct RMQ {
vector<vector<T>> jmp;
RMQ(){}
RMQ(const vector<T>& V) : jmp(1, V) {
for (int pw = 1, k = 1; pw * 2 <= sz(V); pw *= 2, ++k) {
jmp.emplace_back(sz(V) - pw * 2 + 1);
rep(j,0,sz(jmp[k]))
jmp[k][j] = min(jmp[k - 1][j], jmp[k - 1][j + pw]);
}
}
T query(int a, int b) {
// assert(a < b); // or return inf if a == b
int dep = 31 - __builtin_clz(b - a);
return min(jmp[dep][a], jmp[dep][b - (1 << dep)]);
}
};
struct LCA {
int T = 0;
vi time, path, ret;
RMQ<int> rmq;
LCA(){}
LCA(vector<vi>& C) : time(sz(C)), rmq((dfs(C,0,-1), ret)) {}
void dfs(vector<vi>& C, int v, int par) {
time[v] = T++;
for (int y : C[v]) if (y != par) {
path.push_back(v), ret.push_back(time[v]);
dfs(C, y, v);
}
}
int lca(int a, int b) {
if (a == b) return a;
tie(a, b) = minmax(time[a], time[b]);
return path[rmq.query(a, b)];
}
//dist(a,b){return depth[a] + depth[b] - 2*depth[lca(a,b)];}
} lca;
const int N = 5e5 + 3;
int n, sz[N];
vector<pii> adj[N];
bool vis[N];
int cen_par[N];
ll depth[N];
ll get_dist(int a, int b){
int l = lca.lca(a, b);
return depth[a] + depth[b] - 2 * depth[l];
}
void dfs_depth(int u, int par = -1){
for(auto [to, w]: adj[u]){
if(to == par) continue;
depth[to] = depth[u] + w;
dfs_depth(to, u);
}
}
void dfs_sz(int u, int par = -1){
sz[u] = 1;
for(auto [to, w]: adj[u]){
if(vis[to] || to == par) continue;
dfs_sz(to, u);
sz[u] += sz[to];
}
}
int find_centroid(int u, int sz_root, int par = -1){
for(auto [to, w]: adj[u]){
if(to == par || vis[to]) continue;
if(sz[to] >= sz_root / 2) return find_centroid(to, sz_root, u);
}
return u;
}
void decompose(int u, int par = -1){
dfs_sz(u);
int cen = find_centroid(u, sz[u]);
cen_par[cen] = par;
vis[cen] = true;
for(auto [to, w]: adj[cen]){
if(vis[to]) continue;
decompose(to, cen);
}
}
void Init(int _n, int *a, int *b, int *d){
n = _n;
vector<vi> adj2(n + 1);
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]});
adj2[a[i]].push_back(b[i]);
adj2[b[i]].push_back(a[i]);
}
lca = LCA(adj2);
vi e{};
decompose(0, e);
// for(int i = 0; i < n; ++i){
// cout << "anc of " << i << ": ";
// for(int x: anc[i])
// cout << x << " ";
// cout << endl;
// }
dfs_depth(0);
}
const ll INF = 1e18;
ll Query(int s, int x[], int t, int y[]){
unordered_map<int, ll> mn;
for(int i = 0; i < s; ++i){
int v = x[i];
int a = v;
while(a != -1){
if(!mn.count(a)) mn[a] = INF;
chmin(mn[a], get_dist(a, v));
a = cen_par[a];
}
}
// cout << "x" << endl;
ll ans = INF;
for(int i = 0; i < t; ++i){
int v = y[i];
int a = v;
while(a != -1){
if(!mn.count(a)) continue;
chmin(ans, mn[a] + get_dist(a, v));
a = cen_par[a];
}
}
// cout << "y" << endl;
return ans;
}
Compilation message
factories.cpp: In function 'void Init(int, int*, int*, int*)':
factories.cpp:145:18: error: cannot convert 'vi' {aka 'std::vector<int>'} to 'int'
145 | decompose(0, e);
| ^
| |
| vi {aka std::vector<int>}
factories.cpp:118:27: note: initializing argument 2 of 'void decompose(int, int)'
118 | void decompose(int u, int par = -1){
| ~~~~^~~~~~~~
