J.java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class J {

    static ArrayList<Integer>[] adj;
    static boolean[] visited;
    static int[] subtreeSize;
    static long globalAnswer = 0;
    static int n, k, K_prime;
    static long[] allCounts;
    static long[] subtreeCounts;

    static void dfsSize(int u, int p) {
        subtreeSize[u] = 1;
        for (int v : adj[u]) {
            if (v != p && !visited[v]) {
                dfsSize(v, u);
                subtreeSize[u] += subtreeSize[v];
            }
        }
    }

    static int getCentroid(int u, int p, int totalSize) {
        for (int v : adj[u]) {
            if (v != p && !visited[v] && subtreeSize[v] > totalSize / 2) {
                return getCentroid(v, u, totalSize);
            }
        }
        return u;
    }

    static int dfsCollect(int u, int p, int dist, long[] counts) {
        counts[dist]++;
        int max_d = dist;
        for (int v : adj[u]) {
            if (v != p && !visited[v]) {
                max_d = Math.max(max_d, dfsCollect(v, u, dist + 1, counts));
            }
        }
        return max_d;
    }

    static long countValidPairs(long[] counts, int max_d, int K_prime) {
        long ans = 0;
        long[] suffix = new long[max_d + 2];

        for (int i = max_d; i >= 0; i--) {
            suffix[i] = suffix[i + 1] + counts[i];
        }

        for (int d1 = 0; d1 <= max_d; d1++) {
            if (counts[d1] == 0) continue;
            int d2_min = Math.max(0, K_prime - d1);
            if (d2_min <= max_d) {
                ans += counts[d1] * suffix[d2_min];
            }
        }

        long self_pairs = 0;
        for (int d = 0; d <= max_d; d++) {
            if (2 * d >= K_prime) {
                self_pairs += counts[d];
            }
        }

        return (ans - self_pairs) / 2;
    }

    static void decompose(int u) {
        dfsSize(u, -1);
        int totalSize = subtreeSize[u];
        int c = getCentroid(u, -1, totalSize);

        visited[c] = true;

        allCounts = new long[totalSize + 1];
        int maxDepthAll = 0;
        allCounts[0] = 1;

        for (int v : adj[c]) {
            if (!visited[v]) {
                subtreeCounts = new long[totalSize + 1];
                int maxDepthSub = 0;

                maxDepthSub = dfsCollect(v, c, 1, subtreeCounts);

                globalAnswer -= countValidPairs(subtreeCounts, maxDepthSub, K_prime);

                for (int d = 1; d <= maxDepthSub; d++) {
                    allCounts[d] += subtreeCounts[d];
                }
                maxDepthAll = Math.max(maxDepthAll, maxDepthSub);
            }
        }

        globalAnswer += countValidPairs(allCounts, maxDepthAll, K_prime);

        for (int v : adj[c]) {
            if (!visited[v]) {
                decompose(v);
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());

        K_prime = n - 1 - k;

        if (K_prime <= 0) {
            out.println((long)n * (n - 1) / 2);
            out.flush();
            return;
        }

        adj = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            adj[i] = new ArrayList<>();
        }

        for (int i = 0; i < n - 1; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken()) - 1;
            int v = Integer.parseInt(st.nextToken()) - 1;
            adj[u].add(v);
            adj[v].add(u);
        }

        visited = new boolean[n];
        subtreeSize = new int[n];

        decompose(0);

        out.println(globalAnswer);
        out.flush();
    }
}