#include<bits/stdc++.h>
#include "race.h"
using namespace std;
#define ll long long
#define F first
#define S second
#define fall(i,a,b) for(int i=a;i<=b;i++)
#define rfall(i,a,b) for(int i=a;i>=b;i--)
#define pb push_back
#define all(x) x.begin(),x.end()
const int MAXN=2e5+10;
const int MAXL=20;
typedef pair<int,int> pii;
int ancestral[MAXN][MAXL],dp[MAXN],k,dep[MAXN];
ll sparse[MAXN][MAXL],ans=1e9;
set<pii> g[MAXN];
map<ll,int> caras[MAXN];
vector<int> child[MAXN],lista[MAXN];
void dfsini(int x,int p){
for(auto [u,j]:g[x])
if(u!=p){
ancestral[u][0]=x;
sparse[u][0]=j;
dep[u]=dep[x]+1;
dfsini(u,x);
}
}
void dfs(int x,int p){
dp[x]=1;
for(auto[u,j]:g[x]) if(u!=p) dfs(u,x),dp[x]+=dp[u];
}
int get_centroid(int x,int p,int sub){
for(auto [u,j]:g[x])
if(u!=p && 2*dp[u]>sub) return get_centroid(u,x,sub);
return x;
}
void build(int x,int p){
dfs(x,p);
int centroid=get_centroid(x,p,dp[x]);
child[p].pb(centroid);
vector<pii> adj(all(g[centroid]));
for(auto [u,j]:adj){
g[u].erase({centroid,j});
g[centroid].erase({u,j});
build(u,centroid);
}
}
pair<ll,ll> dist(int a,int b){
if(dep[a]<dep[b]) swap(a,b);
ll r=0,r1=0;
rfall(i,MAXL-1,0){
if(dep[a]-(1<<i)>=dep[b]){
r+=(1<<i);
r1+=sparse[a][i];
a=ancestral[a][i];
}
}
if(a==b) return{r,r1};
rfall(i,MAXL-1,0){
if(ancestral[a][i]!=ancestral[b][i] && ancestral[a][i] && ancestral[b][i]){
r+=2*(1<<i);
r1+=sparse[a][i]+sparse[b][i];
a=ancestral[a][i];
b=ancestral[b][i];
}
}
r+=2,r1+=sparse[a][0]+sparse[b][0];
return{r,r1};
}
void calc(int x){
lista[x].pb(x);
for(auto u:child[x]){
calc(u);
for(auto i:lista[u]){
auto d=dist(x,i);
int y=caras[x][k-d.S];
if(y!=0) ans=min(ans,d.F+y);
}
for(auto i:lista[u]){
auto d=dist(x,i);
if(caras[x][d.S]==0) caras[x][d.S]=d.F;
else caras[x][d.S]=min(caras[x][d.S],d.F);
lista[x].pb(i);
}
}
if(caras[x][k]!=0) ans=min(ans,caras[x][k]);
}
int best_path(int n, int K, int H[][2], int L[]){
fall(i,0,n-2){
int a=H[i][0],b=H[i][1]; a++,b++;
g[a].insert({b,L[i]});
g[b].insert({a,L[i]});
}
k=K;
dfsini(1,0);
fall(j,1,MAXL-1)
fall(i,1,n) ancestral[i][j]=ancestral[ancestral[i][j-1]][j-1],sparse[i][j]=sparse[i][j-1]+sparse[ancestral[i][j-1]][j-1];
build(1,0);
calc(child[0][0]);
return(ans==1e9?-1:ans);
}
Compilation message (stderr)
race.cpp: In function 'void calc(int)':
race.cpp:99:47: error: no matching function for call to 'min(std::map<long long int, int>::mapped_type&, long long int&)'
99 | else caras[x][d.S]=min(caras[x][d.S],d.F);
| ~~~^~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/13/algorithm:60,
from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:51,
from race.cpp:1:
/usr/include/c++/13/bits/stl_algobase.h:233:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
233 | min(const _Tp& __a, const _Tp& __b)
| ^~~
/usr/include/c++/13/bits/stl_algobase.h:233:5: note: template argument deduction/substitution failed:
race.cpp:99:47: note: deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
99 | else caras[x][d.S]=min(caras[x][d.S],d.F);
| ~~~^~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algobase.h:281:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
281 | min(const _Tp& __a, const _Tp& __b, _Compare __comp)
| ^~~
/usr/include/c++/13/bits/stl_algobase.h:281:5: note: template argument deduction/substitution failed:
race.cpp:99:47: note: deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
99 | else caras[x][d.S]=min(caras[x][d.S],d.F);
| ~~~^~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/13/algorithm:61:
/usr/include/c++/13/bits/stl_algo.h:5775:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(initializer_list<_Tp>)'
5775 | min(initializer_list<_Tp> __l)
| ^~~
/usr/include/c++/13/bits/stl_algo.h:5775:5: note: template argument deduction/substitution failed:
race.cpp:99:47: note: mismatched types 'std::initializer_list<_Tp>' and 'int'
99 | else caras[x][d.S]=min(caras[x][d.S],d.F);
| ~~~^~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algo.h:5785:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(initializer_list<_Tp>, _Compare)'
5785 | min(initializer_list<_Tp> __l, _Compare __comp)
| ^~~
/usr/include/c++/13/bits/stl_algo.h:5785:5: note: template argument deduction/substitution failed:
race.cpp:99:47: note: mismatched types 'std::initializer_list<_Tp>' and 'int'
99 | else caras[x][d.S]=min(caras[x][d.S],d.F);
| ~~~^~~~~~~~~~~~~~~~~~~
race.cpp:104:35: error: no matching function for call to 'min(long long int&, std::map<long long int, int>::mapped_type&)'
104 | if(caras[x][k]!=0) ans=min(ans,caras[x][k]);
| ~~~^~~~~~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algobase.h:233:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
233 | min(const _Tp& __a, const _Tp& __b)
| ^~~
/usr/include/c++/13/bits/stl_algobase.h:233:5: note: template argument deduction/substitution failed:
race.cpp:104:35: note: deduced conflicting types for parameter 'const _Tp' ('long long int' and 'std::map<long long int, int>::mapped_type' {aka 'int'})
104 | if(caras[x][k]!=0) ans=min(ans,caras[x][k]);
| ~~~^~~~~~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algobase.h:281:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
281 | min(const _Tp& __a, const _Tp& __b, _Compare __comp)
| ^~~
/usr/include/c++/13/bits/stl_algobase.h:281:5: note: template argument deduction/substitution failed:
race.cpp:104:35: note: deduced conflicting types for parameter 'const _Tp' ('long long int' and 'std::map<long long int, int>::mapped_type' {aka 'int'})
104 | if(caras[x][k]!=0) ans=min(ans,caras[x][k]);
| ~~~^~~~~~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algo.h:5775:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(initializer_list<_Tp>)'
5775 | min(initializer_list<_Tp> __l)
| ^~~
/usr/include/c++/13/bits/stl_algo.h:5775:5: note: template argument deduction/substitution failed:
race.cpp:104:35: note: mismatched types 'std::initializer_list<_Tp>' and 'long long int'
104 | if(caras[x][k]!=0) ans=min(ans,caras[x][k]);
| ~~~^~~~~~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algo.h:5785:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(initializer_list<_Tp>, _Compare)'
5785 | min(initializer_list<_Tp> __l, _Compare __comp)
| ^~~
/usr/include/c++/13/bits/stl_algo.h:5785:5: note: template argument deduction/substitution failed:
race.cpp:104:35: note: mismatched types 'std::initializer_list<_Tp>' and 'long long int'
104 | if(caras[x][k]!=0) ans=min(ans,caras[x][k]);
| ~~~^~~~~~~~~~~~~~~~~