#include <bits/stdc++.h> using namespace std; using ll = long long; vector<vector<pair<ll, int>>> g; vector<bool> dead; vector<int> subtree_size; int ans = INT_MAX; void compute_subtree_size(int u, int p) { subtree_size[u] = 1; for (auto[w, v] : g[u]) { if (v == p || dead[v]) continue; compute_subtree_size(v, u); subtree_size[u] += subtree_size[v]; } } int find_centroid(int u, int p) { int mx_val = 0, mx_node = 0; for (auto[w, v] : g[u]) { if (v == p || dead[v]) continue; if (subtree_size[v] > mx_val) { mx_val = subtree_size[v]; mx_node = v; } } if (mx_val <= subtree_size[u]/2) return u; else return find_centroid(mx_node, u); } unordered_map<ll, int> mp; vector<pair<ll, int>> vals; void dfs(int u, int p, ll dist, int path) { vals.push_back({dist, path}); for (auto[w, v] : g[u]) { if (v == p || dead[v]) continue; dfs(v, u, dist+w, path+1); } } void decompose(int u, ll K) { compute_subtree_size(u, -1); int centroid = find_centroid(u, -1); for (auto[w, v] : g[centroid]) { if (dead[v]) continue; dfs(v, centroid, w, 1); for (auto vals_i : vals) if (mp.count(K-vals_i.first)) ans = min(ans, vals_i.second + mp[K-vals_i.first]); for (auto vals_i : vals) { if (!mp.count(vals_i.first)) mp[vals_i.first] = vals_i.second; else mp[vals_i.first] = min(mp[vals_i.first], vals_i.second); } vals.clear(); } if (mp.count(K)) ans = min(ans, mp[K]); mp.clear(); dead[centroid] = true; for (auto[w, v] : g[centroid]) { if (dead[v]) continue; decompose(v, K); } } int best_path(int N, int K, int H[][2], int L[]) { g = vector<vector<pair<ll, int>>>(N); dead = vector<bool>(N); subtree_size = vector<int>(N); for (int i = 0; i < N-1; i++) { g[H[i][0]].push_back({L[i], H[i][1]}); g[H[i][1]].push_back({L[i], H[i][0]}); } decompose(0, K); int ans1 = ans; g.clear(); dead.clear(); subtree_size.clear(); ans = INT_MAX; return ans1; } // int main() // { // int N = 4; // int K = 3; // int H[3][2] = {{0, 1}, {1, 2}, {1, 3}}; // int L[3] = {1, 2, 4}; // cout << best_path(N, K, H, L); // }