#include <bits/stdc++.h>
#define task "brianthecrab"
#define int long long
#define pii pair <int, int>
#define fi first
#define se second
#define szf sizeof
#define sz(s) (int)((s).size())
#define all(v) (v).begin(), (v).end()
using namespace std;
template <class T> void mini (T &t, T f) {if (t > f) t = f;}
template <class T> void maxi (T &t, T f) {if (t < f) t = f;}
const int N = 1e6 + 5;
const int inf = 1e18 + 7;
const int mod = 1e9 + 7;
int n, k;
int tt;
struct CD {
int sz[N], edgecnt[N], exist[N];
set <pii> G[N];
// get sz
int dfs (int u, int p) {
sz[u] = 1;
for (auto [v, dis] : G[u]) {
if (v == p) {
continue;
}
sz[u] += dfs (v, u);
}
return sz[u];
}
// find centroid
int centroid (int u, int p, int nn) {
for (auto [v, dis] : G[u]) {
if (v == p) {
continue;
}
if (sz[v] > nn / 2) {
return centroid (v, u, nn);
}
}
return u;
}
int dfs2 (int u, int p, int d, int cnt, int t, vector <pii> &vv) {
int want = k - d;
int ans = inf;
if (want >= 0 && exist[want] == t) {
mini (ans, cnt + edgecnt[want]);
}
if (d <= k) {
vv.push_back ({d, cnt});
for (auto [v, dis] : G[u]) {
if (v == p) {
continue;
}
int cur = dfs2 (v, u, d + dis, cnt + 1, t, vv);
mini (ans, cur);
}
}
return ans;
}
int sol (int u, int p) {
int nn = dfs (u, p);
int c = centroid (u, p, nn);
int ans = inf;
int t = ++t;
exist[0] = t;
edgecnt[0] = 0;
for (auto [v, dis] : G[c]) {
vector <pii> tmp;
int cur = dfs2 (v, c, dis, 1, t, tmp);
mini (ans, cur);
for (auto [v1, dis1] : tmp) {
if (exist[v1] != t || (exist[v1] == t && edgecnt[v1] > dis1)) {
exist[v1] = t;
edgecnt[v1] = dis1;
}
}
}
vector <pii> tmp (G[c].begin (), G[c].end ());
for (auto [v, dis] : tmp) {
G[c].erase ({v, dis});
G[v].erase ({c, dis});
int cur = sol (v, c);
mini (ans, cur);
}
return ans;
}
} T;
signed main () {
ios_base :: sync_with_stdio (0);
cin.tie (0);
cout.tie (0);
if (fopen (task".inp", "r")) {
freopen (task".inp", "r", stdin);
freopen (task".out", "w", stdout);
}
cin >> n >> k;
for (int i = 1; i <= n - 1; i ++) {
int u, v, w;
cin >> u >> v >> w;
T.G[u].insert ({v, w});
T.G[v].insert ({u, w});
}
tt = 0;
int ans = T.sol (0, -1);
cout << (ans == inf ? - 1 : ans);
return 0;
}
// hmvncvdqdela
Compilation message
race.cpp: In member function 'long long int CD::sol(long long int, long long int)':
race.cpp:79:17: warning: operation on 't' may be undefined [-Wsequence-point]
79 | int t = ++t;
| ^~~
race.cpp: In function 'int main()':
race.cpp:109:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
109 | freopen (task".inp", "r", stdin);
| ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
race.cpp:110:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
110 | freopen (task".out", "w", stdout);
| ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
race.cpp: In member function 'long long int CD::sol(long long int, long long int)':
race.cpp:79:19: warning: 't' may be used uninitialized in this function [-Wmaybe-uninitialized]
79 | int t = ++t;
| ^
/usr/bin/ld: /tmp/cctzPc50.o: in function `main':
race.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccHbUCi2.o:grader.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccHbUCi2.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
