#include<bits/stdc++.h>
using namespace std;
#define ternal asdasf
const long long N = 2e5 + 5;
long long n , k , ans = 1e9;
long long sz[N];
bool is_centroid[N];
vector < pair < long long , long long > > g[N];
map < long long , long long > ternal , global;
void DFS(long long u , long long par)
{
sz[u] = 1;
for(auto v: g[u])
if(v.first != par && !is_centroid[v.first])
{
DFS(v.first , u);
sz[u] += sz[v.first];
}
}
long long find_centroid(long long u , long long tree_sz , long long par)
{
for(auto v: g[u])
if(v.first != par && !is_centroid[v.first] && sz[v.first] > tree_sz / 2)
return find_centroid(v.first , tree_sz , u);
return u;
}
void solve(long long u , long long par , long long h , long long len)
{
if(ternal.find(h) == ternal.end())
ternal[h] = len;
else
ternal[h] = min(ternal[h] , len);
if(global.find(k - h) != global.end())
ans = min(ans , len + global[k - h]);
for(auto v: g[u])
if(v.first != par && !is_centroid[v.first])
solve(v.first , u , h + v.second , len + 1);
}
void build_centroid(long long u)
{
DFS(u , -1);
long long centroid = find_centroid(u , sz[u] , -1);
global[0] = 0;
for(auto v: g[centroid])
if(!is_centroid[v.first])
{
solve(v.first , centroid , v.second , 1);
for(auto x: ternal)
{
if(global.find(x.first) == global.end())
global[x.first] = x.second;
else
global[x.first] = min(global[x.first] , x.second);
}
ternal.clear();
}
global.clear();
is_centroid[centroid] = true;
for(auto v: g[centroid])
if(!is_centroid[v.first])
build_centroid(v.first);
}
long long best_path(long long m , long long p , long long h[][2] , long long l[])
{
k = p;
n = m;
for(long long i = 0 ; i <= n - 1 ; i++)
{
h[i][0]++;
h[i][1]++;
g[h[i][0]].push_back({h[i][1] , l[i]});
g[h[i][1]].push_back({h[i][0] , l[i]});
}
build_centroid(1);
if(ans == 1e9)
return -1;
else
return ans;
}
//main()
//{
// //freopen("centroid.INP","r",stdin);
//// freopen("BIEUTHUCNT.OUT","w",stdout);
// ios::sync_with_stdio(0);
// cin.tie(0);
// cin >> n >> k;
// for(long long i = 1 ; i <= n - 1 ; i++)
// {
// long long u , v , w;
// cin >> u >> v >> w;
// u++;v++;
// g[u].push_back({v , w});
// g[v].push_back({u , w});
// }
// build_centroid(1);
// if(ans == 1e9)
// cout << "-1";
// else
// cout << ans << "\n";
//}
Compilation message
/usr/bin/ld: /tmp/ccS2i8Py.o: in function `main':
grader.cpp:(.text.startup+0x28): undefined reference to `best_path(int, int, int (*) [2], int*)'
collect2: error: ld returned 1 exit status
