#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
const long long INF = 1e18;
const int NMAX = 500500;
vector<pair<int,int>> g[NMAX];
vector<int> sz, best, dp, tin, tout, us, par;
int up[21][NMAX];
int tim;
vector<map<int,long long>> dist;
void dfs(int v,int p,long long sum){
tin[v]=tim++;
dp[v]=sum;
up[0][v]=p;
for(int i=1;i<=20;i++)
up[i][v]=up[i-1][up[i-1][v]];
for(auto [to,c]:g[v]){
if(to!=p)
dfs(to,v,sum+c);
}
tout[v]=tim;
}
void precalc(int v,int p){
sz[v]=1;
for(auto [to,_]:g[v]){
if(to!=p && !us[to]){
precalc(to,v);
sz[v]+=sz[to];
}
}
}
int get(int v,int p,int n){
for(auto k:g[v]){
if(sz[k.first]>n/2 && k.first!=p && !us[k.first])
return get(k.first,v,n);
}
return v;
}
bool check(int a,int b){
return tin[a]<=tin[b] && tout[b]<=tout[a];
}
int lca(int a,int b){
if(check(a,b)) return a;
if(check(b,a)) return b;
for(int i=20;i>=0;i--){
if(!check(up[i][a],b))
a=up[i][a];
}
return up[0][a];
}
long long disti(int a,int b){
return dp[a]+dp[b]-2*dp[lca(a,b)];
}
void build(int v,int p){
precalc(v,-1);
int c=get(v,-1,sz[v]);
us[c]=1;
par[c]=p;
for(auto k:g[c]){
if(!us[k.first])
build(k.first,c);
}
}
void upd(int v,int x){
best[v]=min(dist[x][v],best[v]);
if(par[v]<0) return;
upd(par[v],x);
}
void upd1(int v,int x){
dist[x][v]=disti(v,x);
if(par[v]<0) return;
upd1(par[v],x);
}
void nulify(int v,int x){
best[v]=INF;
if(par[v]<0) return;
nulify(par[v],x);
}
long long ans;
void res(int v,int x){
ans=min(dist[x][v]+best[v],ans);
if(par[v]<0) return;
res(par[v],x);
}
// ============================
// Батч API
// ============================
void Init(int N, int A[], int B[], int D[]) {
tim = 0;
g.assign(N, {});
dp.assign(N,0);
tin.assign(N,0);
tout.assign(N,0);
sz.assign(N,0);
best.assign(N, INF);
us.assign(N,0);
par.assign(N,-1);
dist.assign(N, map<int,long long>());
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]});
}
dfs(0,0,0);
build(0,-1);
for(int i=0;i<N;i++)
upd1(i,i);
}
long long Query(int S, int X[], int T, int Y[]) {
for(int i=0;i<S;i++)
upd(X[i], X[i]);
ans = INF;
for(int i=0;i<T;i++)
res(Y[i], Y[i]);
for(int i=0;i<S;i++)
nulify(X[i], X[i]);
return ans;
}
Compilation message (stderr)
factories.cpp: In function 'void upd(int, int)':
factories.cpp:75:16: error: no matching function for call to 'min(std::map<int, long long int>::mapped_type&, __gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type&)'
75 | best[v]=min(dist[x][v],best[v]);
| ~~~^~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/13/algorithm:60,
from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:51,
from factories.cpp:2:
/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:
factories.cpp:75:16: note: deduced conflicting types for parameter 'const _Tp' ('long long int' and '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'})
75 | best[v]=min(dist[x][v],best[v]);
| ~~~^~~~~~~~~~~~~~~~~~~~
/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:
factories.cpp:75:16: note: deduced conflicting types for parameter 'const _Tp' ('long long int' and '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'})
75 | best[v]=min(dist[x][v],best[v]);
| ~~~^~~~~~~~~~~~~~~~~~~~
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:
factories.cpp:75:16: note: mismatched types 'std::initializer_list<_Tp>' and 'long long int'
75 | best[v]=min(dist[x][v],best[v]);
| ~~~^~~~~~~~~~~~~~~~~~~~
/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:
factories.cpp:75:16: note: mismatched types 'std::initializer_list<_Tp>' and 'long long int'
75 | best[v]=min(dist[x][v],best[v]);
| ~~~^~~~~~~~~~~~~~~~~~~~
factories.cpp: In function 'void nulify(int, int)':
factories.cpp:87:13: warning: overflow in conversion from 'long long int' to '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} changes value from '1000000000000000000' to '-1486618624' [-Woverflow]
87 | best[v]=INF;
| ^~~
factories.cpp: In function 'void Init(int, int*, int*, int*)':
factories.cpp:105:7: error: request for member 'assign' in 'g', which is of non-class type 'std::vector<std::pair<int, int> > [500500]'
105 | g.assign(N, {});
| ^~~~~~
factories.cpp:110:20: warning: overflow in conversion from 'long long int' to 'std::vector<int>::value_type' {aka 'int'} changes value from '1000000000000000000' to '-1486618624' [-Woverflow]
110 | best.assign(N, INF);
| ^~~