#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 comp) { for (auto[w, v] : g[u]) { if (v == p || dead[v]) continue; if (subtree_size[v] > comp/2) return find_centroid(v, u, comp); } return 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, subtree_size[u]); mp[0] = 0; 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(); } 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 = 11; // int K = 12; // int H[10][2] = {{0, 1}, {0, 2}, {2, 3}, {3, 4}, {4, 5}, {0, 6}, {6, 7}, {6, 8}, {8, 9}, {8, 10}}; // int L[10] = {3, 4, 5, 4, 6, 3, 2, 5, 6, 7}; // cout << best_path(N, K, H, L); // }

/usr/bin/ld: /usr/lib/gcc/x86_64-linux-gnu/13/../../../x86_64-linux-gnu/crt1.o: in function `_start':
(.text+0x1b): undefined reference to `main'
collect2: error: ld returned 1 exit status