#include <bits/stdc++.h> #include "race.h" using namespace std; #define TASK "long" #define fi first #define se second #define ll long long #define ALL(x) (x).begin(), (x).end() #define GETBIT(mask, i) ((mask) >> (i) & 1) #define MASK(i) ((1LL) << (i)) #define SZ(x) ((int)(x).size()) #define CNTBIT(mask) __builtin_popcount(mask) template<class X, class Y> bool maximize(X &x, Y y){ if (x < y) {x = y; return true;} return false;}; template<class X, class Y> bool minimize(X &x, Y y){ if (x > y) {x = y; return true;} return false;}; typedef pair<int, int> ii; const int N = 2e5 + 2; const int inf = 1e9 + 7; const long long INF = (long long)1e18 + 7; const int mod = 1e9 + 7; void add(int &x, int y) {x += y; if (x >= mod) x -= mod;} void sub(int &x, int y) {x -= y; if (x < 0) x += mod;} int mul(int x, int y) {return 1LL * x * y % mod;} int calPw(int x, int y) { int ans = 1; for(; y > 0; y >>= 1) { if (y & 1) ans = 1LL * ans * x % mod; x = 1LL * x * x % mod; } return ans; } // -----------------------------------------// vector<ii> adj[N]; void read() { } map<int, int> mp[N]; int dfs(int u, int p, int K) { int ans = inf; pair<int, int> middle = {inf, inf}; mp[u][0] = 0; for(auto [v, c]: adj[u]) if (v != p) { ans = min(ans, dfs(v, u, K)); for(auto x: mp[v]) { if (K - x.fi - c >= 0 && mp[u].count(K - x.fi - c)) ans = min(ans, x.se + 1 + mp[u][K - x.fi - c]); } for(auto x: mp[v]) { if (x.fi * 2 == K) { if (x.se < middle.fi) { middle.se = middle.fi; middle.fi = x.se; } else middle.se = min(middle.se, x.se); } // cout << u << ' ' << v << ' ' << x.fi << ' ' << x.se << ' ' << c << endl; if (mp[u].count(x.fi + c) == 0) mp[u][x.fi + c] = x.se + 1; else mp[u][x.fi] = min(mp[u][x.fi + c], x.se + 1); } } if (middle.fi < inf && middle.se < inf) { ans = min(ans, middle.fi + middle.se + 2); } return ans; } int best_path(int N, int K, int H[][2], int L[]) { for(int i = 0; i < N - 1; i++) { adj[H[i][0]].push_back({H[i][1], L[i]}); adj[H[i][1]].push_back({H[i][0], L[i]}); } int ans = dfs(0, -1, K); return ans == inf ? -1 : ans; } // int H[N][2], L[N]; // int n, K; // void solve() { // cin >> n >> K; // for(int i = 0; i < n - 1; i++) cin >> H[i][0] >> H[i][1]; // for(int i = 0; i < n - 1; i++) cin >> L[i]; // cout << best_path(n, K, H, L); // } // signed main() { // ios_base::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); // } // int test = 1; // // cin >> test; // while(test--) { // read(); // solve(); // } // return 0; // } // struct Point { // int x, y; // void read(){ scanf("%d %d", &x, &y); } // Point operator +(const Point& b) const { return Point{x+b.x, y+b.y}; } // Point operator -(const Point& b) const { return Point{x-b.x, y-b.y}; } // ll operator *(const Point& b) const { return (ll) x * b.y - (ll) y * b.x; } // bool operator <(const Point& b) const { return x == b.x ? y < b.y : x < b.x; } // void operator +=(const Point& b) { x += b.x; y += b.y; } // void operator -=(const Point &b) { x -= b.x; y -= b.y; } // void operator *=(const int k) { x *= k; y *= k; } // ll cross(const Point& b, const Point& c) const { // return (b - *this) * (c - *this); // } // };