#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define rep(i,j,k) for (int i = j; i < (k); i++)
#define in(mp, v) (mp.find(v) != mp.end())
#define smx(a, b) a = max(a, b)
#define smn(a, b) a = min(a, b)
#define pb push_back
const ll MOD = 1e9 + 7;
const ld EPS = 1e-9;
struct decomp {
vector<vi> adj;
vector<vector<pair<int, ll>>> adjw;
vector<bool> r;
vi s, cpar;
decomp(int n): adj(n+1), adjw(n+1), r(n+1), s(n+1), cpar(n+1) {}
int dfs(int n, int p = 0) {
s[n] = 1;
for (int x : adj[n])
if (x != p && !r[x]) s[n] += dfs(x, n);
return s[n];
}
int get_centroid(int n, int ms,
int p = 0)
{
for (int x : adj[n])
if (x != p && !r[x])
if (s[x] * 2 > ms) return get_centroid(x, ms, n);
return n;
}
vector<int> vis, best;
int dfs2(int x, int p, int C, int k, int d, vector<pii> &res) {
if (k < 0) return MOD;
int ans = MOD;
if (vis[k] == C) smn(ans, best[k]+d);
res.pb({k, d});
for (auto &[v, w] : adjw[x]) {
if (v == p || v == C) continue;
smn(ans, dfs2(v, x, C, k-w, d+1, res));
}
return ans;
}
int centroid(int k, int n = 1, int p = 0) {
int C = get_centroid(n, dfs(n));
cpar[C] = p;
int ans = MOD;
for (auto &[v, w] : adjw[C]) {
vector<pii> res;
smn(ans, dfs2(v, C, C, k-w, 1, res));
for (auto &[nk, nd] : res) {
nk = k-nk;
if (vis[nk] != C || best[nk] > nd) {
vis[nk] = C;
best[nk] = nd;
}
}
}
r[C] = 1;
for (int x : adj[C])
if (!r[x]) smn(ans, centroid(k, x, C));
return ans;
}
};
int main() {
cin.tie(0)->sync_with_stdio(0);
int n, k; cin >> n >> k;
decomp d(n);
rep(i, 0, n-1) {
int u, v; ll w; cin >> u >> v >> w; u++; v++;
d.adj[u].pb(v); d.adj[v].pb(u);
d.adjw[u].pb({v, w}); d.adjw[v].pb({u, w});
}
d.vis.resize(k+1, -1);
d.best = vi(k+1, MOD);
d.best[0] = 0;
cout << d.centroid(k) << '\n';
}
Compilation message
/usr/bin/ld: /tmp/cc4XGhcw.o: in function `main':
race.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccMNZS5v.o:grader.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccMNZS5v.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
