Show problems as
Classic problem #3067MediumArrayTreeDepth-First Search

Count Pairs of Connectable Servers in a Weighted Tree Network

Real-world version: Relay Pairs Through Each Hub
Tracked in this browser only
Read Count Pairs of Connectable Servers in a Weighted Tree Network on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A campus network wires n relay nodes, numbered 0 to n - 1, into a tree. The wiring arrives as a weighted edge list links, where links[i] = [a, b, w] means a cable of length w runs between node a and node b. Since the network is a tree, links holds n - 1 cables and exactly one route runs between any two nodes. The distance between two nodes is the total cable length along that route.

The gear runs at a fixed cadence hop. Fix a node c and call it the hub. An unordered pair of nodes {a, b} relays through c when all of the following hold:

  • a, b and c are three different nodes;
  • the route from a to b passes through c;
  • the distance from a to c is a multiple of hop;
  • the distance from c to b is a multiple of hop.

Produce a list of length n whose entry at position c is how many unordered pairs relay through node c.

Examples

Example 1

Input
links = [[0, 1, 2], [0, 2, 2], [1, 3, 2], [2, 4, 4]], hop = 2
Output
[4, 3, 3, 0, 0]

From node 0 the branch through node 1 holds nodes 1 and 3 at distances 2 and 4, and the branch through node 2 holds nodes 2 and 4 at distances 2 and 6; all four distances are multiples of 2, so the four pairs taking one node from each branch all relay through node 0. Node 1 has nodes 0, 2 and 4 at distances 2, 4 and 8 on one side and node 3 at distance 2 on the other, giving three pairs, and node 2 works out the same way. Nodes 3 and 4 each have a single cable, so no route can enter and leave them.

Example 2

Input
links = [[0, 1, 3], [1, 2, 3], [0, 3, 1]], hop = 3
Output
[0, 1, 0, 0]

At node 1 the pair {0, 2} qualifies: node 0 is 3 away, node 2 is 3 away and the route between them runs through node 1. At node 0 the only other branch holds node 3 at distance 1, which is not a multiple of 3, so nothing pairs there. Nodes 2 and 3 are ends of the network.

Example 3

Input
links = [[0, 1, 5]], hop = 1
Output
[0, 0]

The network has two nodes, so no pair can supply two endpoints distinct from the hub and both counts are zero.

Constraints

  • 1 <= links.length <= 999
  • links[i].length == 3
  • 0 <= links[i][j] <= 10^6
  • 1 <= hop <= 10^6
  • Writing n for links.length + 1, we have 2 <= n <= 1000 and every cable is [a_i, b_i, w_i] with 0 <= a_i, b_i < n and 1 <= w_i <= 10^6.
  • links is guaranteed to describe a tree.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def relay_pairs(links: list[list[int]], hop: int) -> list[int]:
Java
public int[] relayPairs(int[][] links, int hop)

More on the same topics