#include <race.h> #include <bits/stdc++.h> using namespace std; typedef long long int ll; const int M = 15e5 + 100; struct Edge{ int next, len; }; int n, k, sub[M], best = M, depth[M]; ll val[M]; vector<Edge> g[M]; map<int, pair<bool, int>> a[M]; void dfs(int v, int p){ int mx = 0, big = -1; for(Edge e: g[v]){ if(e.next != p && sub[e.next] > mx){ mx = sub[e.next]; big = e.next; } } for(Edge e: g[v]){ if(e.next != p && e.next != big) dfs(e.next, v); } if(big > -1) dfs(big, v), a[v].swap(a[big]); a[v][val[v]].first = 1; a[v][val[v]].second = depth[v]; for(Edge e: g[v]){ if(e.next != big && e.next != p){ for(auto p: a[e.next]){ if(a[v][k - p.first + 2 * val[v]].first == 1){ best = min(best, p.second.second + a[v][k - p.first + 2 * val[v]].second - depth[v] * 2); } if(a[v][p.first].first == 0){ a[v][p.first] = {1, p.second.second}; }else a[v][p.first].second = min(a[v][p.first].second, p.second.second); } } } if(a[v][k + val[v]].first == 1){ best = min(best, a[v][k + val[v]].second - depth[v]); } } void init(int v, int p, ll d, int dd){ sub[v] = 1; val[v] = d; depth[v] = dd; for(Edge e: g[v]){ if(e.next != p){ init(e.next, v, d + e.len, dd + 1); sub[v] += sub[e.next]; } } } int best_path(int N, int K, int H[][2], int L[]) { best = N; n = N; k = K; Edge e; for(int i = 0; i < n-1; ++i){ e.next = H[i][1]; e.len = L[i]; g[H[i][0]].push_back(e); e.next = H[i][0]; g[H[i][1]].push_back(e); } init(0, 0, 0, 0); dfs(0, 0); return best; }