#include "race.h"
#include <bits/stdc++.h>
#define int long long
#define FAST_READ ios_base::sync_with_stdio(0);cin.tie(0);
#define SIZE 200001
#define INF INT_MAX
#define F first
#define S second
#define in(a) scanf("%d",&a);
#define outn(a) printf("%d\n",&a);
#define outs(a) printf("%d ",&a);
using namespace std;
int root , n , k , x , y , w , used[SIZE] , dp[SIZE] , co , cent = -1 , we , ans = -1;
vector< pair<int,int> >v[SIZE];
map< int , int > mp;
bool f = true;
void init() {
for (int i = 1;i<=n;i++) {
if (used[i] < 5 && used[i] > 0)used[i] = 0;
}
}
void dfs(int s,int p) {
co++;
used[s] = 1;
int sz = v[s].size();
for (int i = 0;i<sz;i++) {
int to = v[s][i].first;
int cost = v[s][i].second;
if (to == p)continue;
if (used[to] >= 1)continue;
we += cost;
dfs(to,s);
}
}
void dfs2(int s,int p) {
used[s] = 2;
dp[s] = 1;
bool f = true;
int sz = v[s].size();
for (int i = 0;i<sz;i++) {
int to = v[s][i].first;
if (used[to] >= 2)continue;
dfs2(to,s);
if (dp[to] > co / 2) f = false;
dp[s] += dp[to];
}
if (f && cent == -1 && co - dp[s] <= co / 2) cent = s;
}
void dfs3(int s,int p,int len,int cst) {
used[s] = 3;
if (cst == k) {
if (ans == -1)ans = len;
else ans = min(ans,len);
return;
}
int sz = v[s].size();
for (int i = 0;i<sz;i++) {
int to = v[s][i].first;
int cost = v[s][i].second;
if (to == p)continue;
if (used[to] >= 3)continue;
dfs3(to,s,len + 1,cst + cost);
}
}
void dfs4(int s,int p,int len,int cst) {
used[s] = 4;
//cout<<s - 1<<" "<<cst<<" "<<k<<endl;
//char aa;
//cin>>aa;
if (cst > k)return;
if (cst == k) {
if (ans == -1)ans = len;
else ans = min(ans,len);
return;
}
else if (mp[k - cst] != 0) {
if (ans == -1)ans = len + mp[k - cst];
else ans = min(ans,len + mp[k - cst]);
}
int sz = v[s].size();
//cout<<sz<<endl;
for (int i = 0;i<sz;i++) {
int to = v[s][i].first;
int cost = v[s][i].second;
if (to == p)continue;
if (used[to] >= 4)continue;
dfs4(to,s,len + 1,cst + cost);
}
if (mp[cst] == 0)mp[cst] = len;
else if (mp[cst] > len)mp[cst] = min(mp[cst],len);
}
int best_path(int N, int K, int h[][2], int l[])
{
k = K;
n = N;
for (int i = 0;i<n - 1;i++) {
x = h[i][0];
y = h[i][1];
x++;
y++;
v[x].push_back({y,l[i]});
v[y].push_back({x,l[i]});
}
while (f) {
f = false;
init();
for (int i = 1;i<=n;i++) {
if (used[i] == 0) {
co = 0; we = 0;
dfs(i , -1);
if (we < k || co == 1) continue;
dp[i] = 0;
cent = -1;
dfs2(i,-1);
if (cent == -1)continue;
f = true;
root = cent;
dfs3(cent,-1,0,0);
mp.clear();
dfs4(cent,-1,0,0);
used[cent] = 5;
}
}
}
return ans;
}
Compilation message
/tmp/ccBRlEbs.o: In function `main':
grader.cpp:(.text.startup+0x20): undefined reference to `best_path(int, int, int (*) [2], int*)'
collect2: error: ld returned 1 exit status
