#include <bits/stdc++.h>
using namespace std;
struct segTree{
int n;
int inf = 1e9;
vector<pair<int,int>> st;
void init(int n){
this->n = n;
st.resize(4*n,{-1,inf});
}
pair<int,int> merge_pair(pair<int,int> &p1,pair<int,int> &p2){
if(p1.second<p2.second){
return p1;
}else{
if(p1.second>p2.second){
return p2;
}
if(p1.first<p2.first){
return p1;
}
return p2;
}
}
void build(int node,int s,int e,vector<pair<int,int>> &v){
if(s==e){
st[node] = v[s];
return;
}
int lc = 2*node + 1;
int rc = lc + 1;
int mid = s + (e-s)/2;
build(lc,s,mid,v);
build(rc,mid+1,e,v);
st[node] = merge_pair(st[lc],st[rc]);
return;
}
pair<int,int> query_min(int node,int s,int e,int l,int r){
if(e<l||s>r){
return {-1,inf};
}
if(s>=l&&e<=r){
return st[node];
}
int lc = 2*node + 1;
int rc = lc + 1;
int mid = s + (e-s)/2;
pair<int,int> le = query_min(lc,s,mid,l,r);
pair<int,int> ri = query_min(rc,mid+1,e,l,r);
return merge_pair(le,ri);
}
};
struct lca_tree{
int n;
int id = 0;
vector<vector<int>> adj;
map<pair<int,int>,int> wei;
vector<pair<int,int>> dfs_arr;
vector<long long> dep,pos,rdep;
segTree seg;
void init(int n,vector<vector<int>> &tree,map<pair<int,int>,int> &weight){
this->n = n;
this->adj = tree;
this->wei = weight;
dep.resize(n+1,0);
rdep.resize(n+1,0);
pos.resize(n+1,1e9);
dfs(0,-1);
seg.init(2*n - 1);
seg.build(0,0,2*n - 2,dfs_arr);
pos_assign();
}
void dfs(int u,int p){
dfs_arr.push_back({u,dep[u]});
for(auto c: adj[u]){
if(c!=p){
dep[c] = dep[u] + 1;
rdep[c] = rdep[u] + wei[{u,c}];
dfs(c,u);
dfs_arr.push_back({u,dep[u]});
}
}
return;
}
void pos_assign(){
for(int i = 0;i<2*n - 1;i++){
pos[dfs_arr[i].first] = min(pos[dfs_arr[i].first],i);
}
}
int lca(int u,int v){
int l = min(pos[u],pos[v]);
int r = max(pos[u],pos[v]);
pair<int,int> ret = seg.query_min(0,0,2*n - 2,l,r);
return ret.first;
}
int dist(int u,int v){
int lca_cur = lca(u,v);
return dep[u] + dep[v] - 2*dep[lca_cur];
}
long long len(int u,int v){
int lca_cur = lca(u,v);
return rdep[u] + rdep[v] - 2*rdep[lca_cur];
}
};
struct centroid_decomposition{
vector<vector<int>> adj;
vector<bool> removed;
vector<int> sub,par;
int n;
void init(int n,vector<vector<int>> &tree){
this->n = n;
this->adj = tree;
removed.resize(n+1,false);
sub.resize(n+1,1);
par.resize(n+1,-1);
build(0,-1);
}
void build(int u,int p){
int sz = dfs(u,p);
int cent = centroid(u,p,sz);
removed[cent] = true;
//cout<<cent<<" ";
par[cent] = p;
for(auto c: adj[cent]){
if(!removed[c]){
build(c,cent);
}
}
return;
}
int dfs(int u,int p){
for(auto c: adj[u]){
if(c!=p&&!removed[c]){
sub[u] += dfs(c,u);
}
}
return sub[u];
}
int centroid(int u,int p,int sz){
for(auto c: adj[u]){
if(c!=p&&!removed[c]){
if(sub[c]>sz/2){
return centroid(c,u,sz);
}
}
}
return u;
}
};
lca_tree lct;
centroid_decomposition cd;
vector<long long> ans;
void Init(int n,int u[],int v[],int l[]){
vector<vector<int>> adj(n+1);
map<pair<int,int>,int> wei;
for(int i = 0;i<n-1;i++){
wei[{u[i],v[i]}] = l[i];
wei[{v[i],u[i]}] = l[i];
adj[u[i]].push_back(v[i]);
adj[v[i]].push_back(u[i]);
}
lct.init(n,adj,wei);
cd.init(n,adj);
ans.resize(n,1e15);
}
long long Query(int s,int c1[],int t,int c2[]){
for(int i = 0;i<s;i++){
int node = c1[i];
while(node!=-1){
ans[node] = min(ans[node],lct.len(c1[i],node));
node = cd.par[node];
}
}
long long fans = 1e15;
for(int i = 0;i<t;i++){
int node = c2[i];
while(node!=-1){
fans = min(fans,lct.len(c2[i],node) + ans[node]);
node = cd.par[node];
}
}
for(int i = 0;i<s;i++){
int node = c1[i];
while(node!=-1){
ans[node] = 1e15;
node = cd.par[node];
}
}
return fans;
}
Compilation message
factories.cpp: In member function 'void lca_tree::pos_assign()':
factories.cpp:87:64: error: no matching function for call to 'min(__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type&, int&)'
87 | pos[dfs_arr[i].first] = min(pos[dfs_arr[i].first],i);
| ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
from /usr/include/c++/10/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
from factories.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:230:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
230 | min(const _Tp& __a, const _Tp& __b)
| ^~~
/usr/include/c++/10/bits/stl_algobase.h:230:5: note: template argument deduction/substitution failed:
factories.cpp:87:64: note: deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
87 | pos[dfs_arr[i].first] = min(pos[dfs_arr[i].first],i);
| ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
from /usr/include/c++/10/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
from factories.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:278:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
278 | min(const _Tp& __a, const _Tp& __b, _Compare __comp)
| ^~~
/usr/include/c++/10/bits/stl_algobase.h:278:5: note: template argument deduction/substitution failed:
factories.cpp:87:64: note: deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
87 | pos[dfs_arr[i].first] = min(pos[dfs_arr[i].first],i);
| ^
In file included from /usr/include/c++/10/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from factories.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3468:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(std::initializer_list<_Tp>)'
3468 | min(initializer_list<_Tp> __l)
| ^~~
/usr/include/c++/10/bits/stl_algo.h:3468:5: note: template argument deduction/substitution failed:
factories.cpp:87:64: note: mismatched types 'std::initializer_list<_Tp>' and 'long long int'
87 | pos[dfs_arr[i].first] = min(pos[dfs_arr[i].first],i);
| ^
In file included from /usr/include/c++/10/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from factories.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3474:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(std::initializer_list<_Tp>, _Compare)'
3474 | min(initializer_list<_Tp> __l, _Compare __comp)
| ^~~
/usr/include/c++/10/bits/stl_algo.h:3474:5: note: template argument deduction/substitution failed:
factories.cpp:87:64: note: mismatched types 'std::initializer_list<_Tp>' and 'long long int'
87 | pos[dfs_arr[i].first] = min(pos[dfs_arr[i].first],i);
| ^
