#include "race.h" #include <bits/stdc++.h> using namespace std; typedef long long int ll; const int M = 2e5 + 100; struct Edge{ int next, len; }; int n, k, sub[M], best = 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]); if(a[v][val[v]].first == 0){ a[v][val[v]].first = 1; }else a[v][val[v]].second = 0; 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); if(a[v][p.first].first == 0){ a[v][p.first] = {1, p.second.second}; }else a[v][val[v]].second = min(a[v][val[v]].second, p.second.second); } } } } void init(int v, int p, ll d){ sub[v] = 1; val[v] = d; for(Edge e: g[v]){ if(e.next != p){ init(e.next, v, d + e.len); 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(1, 0, 0); dfs(1, 0); return best; }