Beacon Pair Distance Problem

Beacon Pair Distance Problem — ExecCode Hard DSA Practice

Solve the Beacon Pair Distance problem on ExecCode. Free online hard DSA practice in Graph. Write and run code in Java, C++, Python — no signup required to run.

Problem description

A mountain range is a tree of watchtowers. Two towers can flash a signal if the unique trail between them has exactly k edges. The ranger wants the number of unordered pairs that can talk at that exact hop distance. On large trees this is centroid decomposition (count distances through each centroid). A Fenwick on the centroid bag makes it fast. Return how many unordered pairs of nodes have distance exactly k. Distance is the number of edges on the unique path. You are given: n — number of towers edges — n-1 tree edges [u, v] k — required hop distance Return the number of unordered pairs at distance k. A node is distance 0 from itself; those pairs are not counted. If k is larger than every path, the answer is 0.

Examples

Input {'n': 4, 'edges': [[0, 1], [0, 2], [2, 3]], 'k': 2}; Output 2. Input {'n': 3, 'edges': [[0, 1], [1, 2]], 'k': 1}; Output 2. Input {'n': 2, 'edges': [[0, 1]], 'k': 5}; Output 0

Constraints

The graph is a tree k >= 0 n >= 1

Practice Beacon Pair Distance free on ExecCode. Browse DSA problems, topic map, and placement guides.