#include "race.h" #include<bits/stdc++.h> #define int long long using namespace std; vector<pair<int, int>> ad[200005]; map<int, int> f[200005]; int lazy[200005], lazyans[200005], curans = 1e9, target; void unite(int u, int v) { if(f[u].size() < f[v].size()){ f[u].swap(f[v]); swap(lazy[u], lazy[v]); swap(lazyans[u], lazyans[v]); } for(pair<int, int> i : f[v]){ i.first += lazy[v]; i.second += lazyans[v]; int targetval = target - i.first - lazy[u]; if(f[u].count(targetval) == 1){ //cerr<<"B"<<u<<" "<<v<<" "<<targetval+lazy[u]<<" "<<i.second<<" "<<lazyans[v]<<" "<<f[u][targetval]<<" "<<lazyans[u]<<endl; curans = min(curans, i.second + f[u][targetval]+lazyans[u]); } } //cerr<<"BBBBBBBBBB"<<u<<" "<<v<<" "<<lazyans[u]<<" "<<lazyans[v]<<endl; for(pair<int, int> i : f[v]){ i.first += lazy[v]; i.second += lazyans[v]; i.first -= lazy[u]; i.second -= lazyans[u]; if(f[u].count(i.first) == 0) f[u][i.first] = i.second; else{ int &val = f[u][i.first]; val = min(val, i.second); } } } bool visited[200005]; void dfs(int u) { visited[u] = 1; f[u][0] = 0; for(pair<int, int> i : ad[u]){ int v = i.first, c = i.second; if(visited[v] == 1) continue; dfs(v); lazy[v] += c; lazyans[v]++; unite(u, v); //cerr<<"A"<<u<<" "<<v<<" "<<c<<" "<<curans<<endl; } //cerr<<"A"<<u<<endl; //for(pair<int, int> i : f[u]) cerr<<i.first+lazy[u]<<" "<<i.second+lazyans[u]<<endl; visited[u] = 0; } int32_t best_path(int32_t n, int32_t k, int32_t H[][2], int32_t L[]) { target = k; for(int i = 0; i < n-1; i++){ int u = H[i][0], v = H[i][1], c = L[i]; ad[u].push_back({v, c}); ad[v].push_back({u, c}); } dfs(1); if(curans < n) return curans; else return -1; }