#ifndef LAK
#include <race.h>
#endif // LAK
#include <bits/stdc++.h>
#define no "NO"
#define yes "YES"
#define F first
#define S second
#define vec vector
#define task "main"
#define ll long long
#define _mp make_pair
#define ii pair<int, int>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define evoid(val) return void(std::cout << val)
#define FOR(i, a, b) for(int i = (a); i <= (b); ++i)
#define FOD(i, b, a) for(int i = (b); i >= (a); --i)
#define unq(x) sort(all(x)); x.resize(unique(all(x)) - x.begin())
using namespace std;
template<typename U, typename V> bool maximize(U &a, V b) {
if (a < b) { a = b; return 1; } return 0;
}
template<typename U, typename V> bool minimize(U &a, V b) {
if (a > b) { a = b; return 1; } return 0;
}
const int N = (int)2e5 + 9;
const int INF = (int)1e9;
const int MOD = (int)1e9 + 7;
int numNode, numDist;
vector<ii> adj[N];
vector<int> newADJ[N];
int child[N], high[N], par[N];
bool del[N];
map<int, ll> dist[N];
map<ll, int> firstMin[N], secondMin[N];
int ans = INF;
int countChild(int u, int p) {
child[u] = 1;
for (auto [v, w] : adj[u]) {
if (v == p || del[v]) continue;
countChild(v, u);
child[u] += child[v];
}
return child[u];
}
int centroid(int u, int p, int m) {
for (auto [v, w] : adj[u]) {
if (v == p || del[v]) continue;
if (child[v] > m / 2) return centroid(v, u, m);
}
return u;
}
void calcDist(int u, int p, int root, int cnt) {
for (auto [v, w] : adj[u]) {
if (v == p || del[v]) continue;
dist[root][v] = dist[root][u] + w;
int curDist = dist[root][v];
if (!firstMin[root].count(curDist) || firstMin[root][curDist] > cnt + 1)
firstMin[root][curDist] = cnt + 1;
else if (!secondMin[root].count(curDist) || secondMin[root][curDist] > cnt + 1)
secondMin[root][curDist] = cnt + 1;
calcDist(v, u, root, cnt + 1);
}
}
int cd(int u) {
int m = countChild(u, 0);
u = centroid(u, 0, m);
del[u] = 1;
firstMin[u][0] = 0;
calcDist(u, 0, u, 0);
for (auto [v, w] : adj[u]) {
if (del[v]) continue;
int x = cd(v);
par[x] = u;
newADJ[u].push_back(x);
newADJ[x].push_back(u);
}
return u;
}
void initDFS(int u, int p) {
for (int v : newADJ[u]) {
if (v == p) continue;
high[v] = high[u] + 1;
initDFS(v, u);
}
}
void calcDFS(int u, int p) {
int parU = par[u];
while (parU != -1) {
int curDist = dist[parU][u];
int curVertices = high[u] - high[parU];
if (curDist <= numDist) {
int remDist = numDist - curDist;
int remVertices;
if (!firstMin[parU].count(remDist)) remVertices = -1;
else {
if (curDist == remDist)
remVertices = (curVertices == firstMin[parU][remDist] ? (secondMin[parU].count(remDist) ? secondMin[parU][remDist] : -1) : firstMin[parU][remDist]);
else
remVertices = firstMin[parU][remDist];
}
if (remVertices != -1) minimize(ans, curVertices + remVertices);
}
parU = par[parU];
}
for (int v : newADJ[u]) {
if (v == p) continue;
calcDFS(v, u);
}
}
int best_path(int n, int k, int h[][2], int l[]) {
numNode = n;
numDist = k;
FOR(i, 0, numNode - 2) {
int u = h[i][0], v = h[i][1];
int w = l[i];
u++;
v++;
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
int root = cd(1);
par[root] = -1;
high[root] = 0;
initDFS(root, -1);
calcDFS(root, -1);
return (ans != INF ? ans : -1);
}
#ifdef LAK
int edge[N][2];
int length[N];
void main_code() {
int numNode, requireDist;
cin >> numNode >> requireDist;
FOR(i, 0, numNode - 2) {
int u, v, l;
cin >> u >> v >> l;
edge[i][0] = u, edge[i][1] = v;
length[i] = l;
}
cout << best_path(numNode, requireDist, edge, length);
}
#endif // LAK
int main() {
ios::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);
}
const bool MULTITEST = 0;
int num_test = 1; if (MULTITEST) cin >> num_test;
while (num_test--) { main_code(); cout << "\n"; }
}
/* Lak lu theo dieu nhac */
Compilation message
race.cpp: In function 'int main()':
race.cpp:171:26: error: 'main_code' was not declared in this scope
171 | while (num_test--) { main_code(); cout << "\n"; }
| ^~~~~~~~~
race.cpp:166:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
166 | freopen(task".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
race.cpp:167:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
167 | freopen(task".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
