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 ```python 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** ```text 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** ```text 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.