#include <bits/stdc++.h>
#define int unsigned int
#define mi(x, y) (x = min(x, y))
#define ma(x, y) (x = max(x, y))
using namespace std;
const int NS = 20004;
vector<pair<int, int>> way[NS];
int n, c;
int dp[20004][20004], cut[20004];
vector<int> srt;
void sol(int x, int uval = 0, int pr = -1){
int mx = 0;
for(auto&nxt:way[x]){
if(nxt.first == pr){
continue;
}
sol(nxt.first, nxt.second, x);
ma(mx, nxt.second);
cut[x] += min(cut[nxt.first], dp[nxt.first][nxt.second]);
}
cut[x] += c * (int)way[x].size();
for(int i = 0; i < (int)srt.size(); ++i){
int val = srt[max({i, mx, uval})];
int sum = val - srt[uval];
if(x == 1) sum = 0;
for(auto&nxt:way[x]){
if(nxt.first == pr){
continue;
}
sum += min(dp[nxt.first][max({i, mx, uval})], cut[nxt.first] + val - srt[nxt.second]);
}
dp[x][i] = sum;
}
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n >> c;
for(int i = 1; i < n; ++i){
int x, y, z; cin >> x >> y >> z;
way[x].push_back({y, z});
way[y].push_back({x, z});
srt.push_back(z);
}
srt.push_back(0);
sort(srt.begin(), srt.end());
for(int i = 1; i <= n; ++i){
for(auto&nxt:way[i]){
nxt.second = lower_bound(srt.begin(), srt.end(), nxt.second) - srt.begin();
}
}
sol(1);
cout << min(cut[1], dp[1][0]) << '\n';
return 0;
}
Compilation message
/usr/bin/ld: /tmp/cc928ubF.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccdJIz7G.o:dango3.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/cc928ubF.o: in function `main':
grader.cpp:(.text.startup+0x111): undefined reference to `Solve(int, int)'
collect2: error: ld returned 1 exit status
