#include "race.h" #include <bits/stdc++.h> using namespace std; const int maxn = 200005; vector <pair <int, long long> > v[maxn]; map <long long, int> m[maxn]; map <long long, int> ::iterator it; long long dist[maxn]; int koraci[maxn]; int ans = 1e9, parent[maxn]; int find (int x){ if (parent[x] == x) return x; return parent[x] = find(parent[x]); } void unite (int x, int y, int lca, int k){ //cout << "unite " << x << " " << y << " " << lca << " " << k << endl; if (m[x].size() < m[y].size()) swap(x, y); parent[y] = x; /* cout << "cvor " << y << endl; for (auto i : m[y]){ cout << i.first << " " << i.second << endl; } cout << "cvor " << x << endl; for (auto i : m[x]){ cout << i.first << " " << i.second << endl; } cout << endl; */ for (auto i : m[y]){ it = m[x].find(k + 2 * dist[lca] - i.first); if (it != m[x].end()) ans = min(ans, m[x][k + 2 * dist[lca] - i.first] + i.second - 2 * koraci[lca]); } for (auto i : m[y]){ if (m[x][i.first] == 0 or (m[x][i.first] > i.second)) m[x][i.first] = i.second; } m[y].clear(); } void dfs (int x, int p, long long k){ for (int i = 0; i < v[x].size(); i++){ int y = v[x][i].first; if (y != p){ dfs(y, x, k); //cout << "spajam " << x << " " << y << endl; int px = find(x); int py = find(y); unite(px, py, x, k); } } } void dfs2 (int x, int p){ for (int i = 0; i < v[x].size(); i++){ int y = v[x][i].first; int d = v[x][i].second; if (y != p){ dist[y] = dist[x] + d; koraci[y] = koraci[x] + 1; dfs2(y, x); } } } int best_path (int n, int k, int h[maxn][2], int l[maxn]){ for (int i = 0; i < n - 1; i++){ v[h[i][0]].push_back({h[i][1], l[i]}); v[h[i][1]].push_back({h[i][0], l[i]}); } dist[0] = 0, koraci[0] = 1; dfs2(0, 0); for (int i = 0; i < n; i++) m[i][dist[i]] = koraci[i], parent[i] = i; dfs(0, 0, k); if (ans == 1e9) return -1; else return ans; } /* int main (void){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n, k, h[maxn][2], l[maxn]; cin >> n >> k; for (int i = 0; i < n - 1; i++) cin >> h[i][0] >> h[i][1] >> l[i]; cout << best_path(n, k, h, l) << endl; return 0; } */