#include <bits/stdc++.h> using namespace std; int best_path(int n, int k, int H[][2], int L[]) { vector<vector<int>> adj(n); for (int i = 0; i < n - 1; i++) { int x = H[i][0]; int y = H[i][1]; adj[x].push_back(y); adj[y].push_back(x); } vector<bool> visited(n); vector<int> sz(n); function<void(int,int)> dfs_sz = [&](int u, int p) { sz[u] = 1; for (auto v : adj[u]) { if (v == p || visited[v]) continue; dfs_sz(v, u); sz[u] += sz[v]; } }; vector<int> dist; function<void(int,int,int)> dfs = [&](int u, int p, int cur) { dist.push_back(cur); for (auto v : adj[u]) { if (v == p || visited[v]) continue; dfs(v, u, cur + 1); } }; function<int(int,int,int)> find_centroid = [&](int u, int p, int size) { for (auto v : adj[u]) { if (v == p || visited[v]) continue; if (sz[v] > size / 2) return find_centroid(v, u, size); } return u; }; vector<int> cnt(n + 1); int ans = 0; function<void(int)> decompose = [&](int u) { dfs_sz(u, -1); int centroid = find_centroid(u, -1, sz[u]); visited[centroid] = true; cnt[0] = 1; for (auto v : adj[centroid]) { if (visited[v]) continue; dist.clear(); dfs(v, centroid, 1); for (auto d : dist) { if (d <= k) ans += cnt[k - d]; } for (auto d : dist) { cnt[d]++; } } for (int i = 0; i <= sz[u]; i++) cnt[i] = 0; for (auto v : adj[centroid]) { if (!visited[v]) decompose(v); } }; decompose(0); return ans; }