#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n,k;
bool used[200002], used_1[200002], used_2[200002];
vector<pair<int,int>>g[200002];
int size[200002];
int tree_centroid;
int best[200002];
const int inf = 1e9;
int ans = 1e9;
/*
void dfs(int v){
used[v]=true;
for(auto x:g[v]){
if(used[x.first])continue;
dfs(x.first);
size[v]+=size[x.first];
}
size[v]++;
}
*/
void dfs(int node, int dad = -1)
{
size[node] = 1;
for (auto it : g[node])
if (!used[it.first] && it.first != dad)
{
dfs(it.first, node);
size[node] += size[it.first];
}
}
void findcentroid(int v, int flo){
used_1[v]=true;
int zib=0;
for(auto x:g[v]){
if(used_1[x.first])continue;
if(size[x.first] - 1 >= flo){
zib++;
findcentroid(x.first, flo);
break;
}
}
if(zib==0)
tree_centroid=v;
}
void dfs2(int x, int p, int cost, int l, vector<pair<int,int>>&to_ans) {
if (cost <= k)
to_ans.push_back(make_pair(cost, l));
for (auto y : g[x]) {
if (used_2[y.first] || y.first == p)continue;
dfs2(y.first, x, cost + y.second, l + 1, to_ans);
}
}
int solve(int node) {
dfs(node);
fill(used_1, used_1 + n, false);
int zibil = size[node] - 1;
findcentroid(node, zibil / 2);
node = tree_centroid;
best[0] = 0;
vector<int>del;
vector<pair<int, int>>to_ans;
for (auto x : g[node]) {
int son = x.first;
int cost = x.second;
if (used_2[son])continue;
to_ans.clear();
dfs2(x.first, node, x.second, 1, to_ans);
for (auto it : to_ans)
ans = min(ans, it.second + best[k - it.first]);
for (auto it : to_ans)
{
best[it.first] = min(best[it.first], it.second);
del.push_back(it.first);
}
}
for (auto it : del)
best[it] = inf;
used_2[node] = true;
for (auto it : g[node])
if (!used_2[it.first])
ans = min(ans, solve(it.first));
return ans;
}
int main(){
cin>>n>>k;
for(int i=1;i<n;i++){
int x,y,z;
cin>>x>>y>>z;
g[x].push_back(make_pair(y,z));
g[y].push_back(make_pair(x,z));
}
for (int i = 0; i <= k; i++)best[i] = inf;
cout << solve(0) << endl;
return 0;
}
Compilation message
race.cpp: In function 'int solve(int)':
race.cpp:77:7: warning: unused variable 'cost' [-Wunused-variable]
int cost = x.second;
^~~~
/tmp/ccHEU6zA.o: In function `main':
race.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccN0I2nK.o:grader.cpp:(.text.startup+0x0): first defined here
/tmp/ccN0I2nK.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
