Count Server Pairs Relayed Through Each Node of a Weighted Tree

A cluster's servers are wired together so that the cabling forms a tree: there are n servers labeled 0 through n - 1, connected by exactly n - 1 cables, and any two servers are joined by exactly one path. Every cable has a positive integer length.

A server c can act as a relay for an unordered pair of servers {a, b} when all of these conditions hold:

• a, b and c are three different servers;
• the path length from c to a is a multiple of signal_speed, and the path length from c to b is also a multiple of signal_speed;
• the path from c to a and the path from c to b have no cable in common.

For every server, count the pairs it can relay.

Function Signature

def count_relayable_pairs(edges: List[List[int]], signal_speed: int) -> List[int]:

Rules

• Each edges[i] = [u, v, w] is an undirected cable of length w between servers u and v. The number of servers is n = len(edges) + 1.
• The path length between two servers is the sum of the cable lengths along the unique path joining them.
• Pairs are unordered: {a, b} and {b, a} are the same pair and are counted once per relay server.
• Return a list result of length n in which result[c] is the number of pairs that server c can relay. Entries are indexed by server label, so the expected output is unique.

Constraints

• 2 <= n <= 1000
• len(edges) == n - 1
• 0 <= u, v <= n - 1 and u != v for every cable
• 1 <= w <= 10^6
• 1 <= signal_speed <= 10^6
• The cables always form a valid tree (connected, no cycles, no repeated cable).
• Any path length is at most 999 * 10^6, which fits in a signed 32-bit integer; any count is at most n * (n - 1) / 2.

Examples

Example 1

Input: edges = [[0,1,2],[1,2,2],[2,3,4]], signal_speed = 2
Output: [0,2,2,0]

The servers form a chain 0 - 1 - 2 - 3, and every path length here is even. Server 1 has server 0 on one side (length 2) and servers 2 and 3 on the other (lengths 2 and 6), so it relays {0, 2} and {0, 3}. Server 2 has servers 1 and 0 on one side (lengths 2 and 4) and server 3 on the other (length 4), so it relays {1, 3} and {0, 3}. A pair on the same side, such as {2, 3} for server 1, does not count because both paths leave server 1 through the same cable. Servers 0 and 3 reach everything through a single cable, so they relay nothing.

Example 2

Input: edges = [[0,1,3],[0,2,6],[0,3,4],[3,4,2]], signal_speed = 3
Output: [3,0,0,0,0]

From server 0, the path lengths to servers 1, 2, 3 and 4 are 3, 6, 4 and 6. Servers 1, 2 and 4 qualify and each is reached through a different cable out of server 0, giving the pairs {1, 2}, {1, 4} and {2, 4}; server 3 does not qualify. From server 3, the lengths to servers 0, 1, 2 and 4 are 4, 7, 10 and 2, none of which is a multiple of 3. Servers 1, 2 and 4 each have a single cable, so they relay nothing.