n radio towers, numbered 0 to n − 1, is wired as a tree: cables[i] = [a, b, w] is a cable of length w between towers a and b. The number of towers is len(cables) + 1.
The signal is refreshed every step units of length, so tower c can act as a relay for a pair of towers a < b when:
- a ≠ c and b ≠ c;
- the path length from c to a and the path length from c to b are both multiples of step;
- the paths from c to a and from c to b share no cable, i.e. they leave c in different directions.
Return an array of length n whose i-th entry is the number of tower pairs that tower i can relay.cables=[[0, 1, 2], [1, 2, 3], [1, 3, 4]], step=2 → [0, 1, 0, 0]
Three branches leave node 1. Node 0 is 2 away and node 3 is 4 away, both multiples of 2; node 2 is 3 away and does not count. That gives one pair, (0, 3).
cables=[[0, 1, 1], [0, 2, 1], [0, 3, 1]], step=1 → [3, 0, 0, 0]
A star centred at 0: any two leaves are in different branches, which makes 3 pairs. Nothing passes through a leaf.
cables=[[0, 1, 1], [1, 2, 1]], step=2 → [0, 0, 0]
Both neighbours of node 1 are 1 away, which is not a multiple of 2. The end nodes have just one branch each.
cables has n − 1 cables and forms a treecables=[[0, 1, 2], [1, 2, 3], [1, 3, 4]], step=2
[0, 1, 0, 0]
Run checks the first 3 tests in your browser. Submit checks all 95 tests on the server, hidden ones included.