#include <bits/stdc++.h>
using namespace std;
const bool multiTest = 0;
#define TASK ""
#define REP(i, n) for(int i = 1; i <= n; i++)
#define FOR(i, a, b) for(auto i = a; i <= b; i++)
#define FORD(i, a, b) for(auto i = a; i >= b; i--)
template<class T> bool maximize(T& a, T b) { if(a < b) return a = b, 1; return 0; }
template<class T> bool minimize(T& a, T b) { if(a > b) return a = b, 1; return 0; }
mt19937 rng(time(0));
const int maxN = (int)2e5 + 7, maxK = (int)1e6 + 7, INF = (int)1e9 + 7;
using ii = pair<int, int>;
int f[maxK], child[maxN];
bool del[maxN];
vector<ii> G[maxN];
vector<int> used;
int numNode, limK;
int getSize(int u, int p = -1) {
child[u] = 1;
for(ii nxt : G[u]) {
int v = nxt.first, w = nxt.second;
if(v == p || del[v]) continue;
child[u] += getSize(v, u);
}
return child[u];
}
int getCentroid(int sz, int u, int p = -1) {
for(ii nxt : G[u]) {
int v = nxt.first;
if(!del[v] && v != p && child[v] > sz) return getCentroid(sz, v, u);
}
return u;
}
int ans = INF;
void calc(int u, bool filling, int dist, int cntEdge, int p = -1) {
if(dist > limK) return;
if(filling) {
minimize(f[dist], cntEdge);
used.push_back(dist);
}
else minimize(ans, f[limK - dist] + cntEdge);
for(ii nxt : G[u]) {
int v = nxt.first, w = nxt.second;
if(del[v] || v == p) continue;
calc(v, filling, dist + w, cntEdge + 1, u);
}
}
void dnc(int x = 1) {
int root = getCentroid(getSize(x) >> 1, x);
//cout << root << endl;
del[root] = 1;
for(ii nxt : G[root]) {
int v = nxt.first, w = nxt.second;
if(del[v]) continue;
calc(v, 0, w, 1);
calc(v, 1, w, 1);
}
for(int d : used) {
f[d] = INF;
}
used.clear();
for(ii nxt : G[root]) {
int v = nxt.first, w = nxt.second;
if(del[v]) continue;
dnc(v);
}
}
void solve(const int& curTest) {
cerr << "\n>TEST #" << curTest << "<\n";
// GET AC PLEASE
cin >> numNode >> limK;
REP(i, numNode - 1) {
int u, v, w;
cin >> u >> v >> w;
u++; v++;
G[u].push_back({v, w});
G[v].push_back({u, w});
}
memset(f, 0x3f, sizeof f);
f[0] = 0;
dnc();
if(ans == INF) {
cout << -1 << endl;
return;
}
cout << ans << endl;
}
signed main() {
cin.tie(0)->ios_base::sync_with_stdio(0);
if(fopen("TASK.INP", "r")) freopen("TASK.INP", "r", stdin);
if(fopen(TASK".INP", "r")) {
freopen(TASK".INP", "r", stdin);
freopen(TASK".OUT", "w", stdout);
}
int nTest = 1;
if(multiTest) cin >> nTest;
for(int iTest = 1; iTest <= nTest; iTest++) solve(iTest);
return 0;
}
Compilation message
race.cpp: In function 'int getSize(int, int)':
race.cpp:26:22: warning: unused variable 'w' [-Wunused-variable]
26 | int v = nxt.first, w = nxt.second;
| ^
race.cpp: In function 'void dnc(int)':
race.cpp:72:22: warning: unused variable 'w' [-Wunused-variable]
72 | int v = nxt.first, w = nxt.second;
| ^
race.cpp: In function 'int main()':
race.cpp:102:36: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
102 | if(fopen("TASK.INP", "r")) freopen("TASK.INP", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
race.cpp:104:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
104 | freopen(TASK".INP", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
race.cpp:105:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
105 | freopen(TASK".OUT", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/ccKmYY4i.o: in function `main':
race.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccJlgCoj.o:grader.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccJlgCoj.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
