#3067
Count Pairs of Connectable Servers in a Weighted Tree Network
specialist · 795 · lc medium +31 · verified · 55.6% accepted · 239 likes · top 49%
Description
An unrooted weighted tree has n vertices (servers) numbered 0 to n - 1, with bidirectional edges given as edges[i] = [ai, bi, weighti]. You are also given signalSpeed. Servers a and b are connectable through server c when:
- a < b, and neither a nor b equals c.
- The tree distance from c to a is divisible by signalSpeed.
- The tree distance from c to b is divisible by signalSpeed.
- The path from c to a and the path from c to b share no edges.
Return an array count of length n where count[i] is the number of pairs connectable through server i.
Example 1:
Input: edges = [[0,1,1],[1,2,5],[2,3,13],[3,4,9],[4,5,2]], signalSpeed = 1
Output: [0,4,6,6,4,0]
Explanation: Since signalSpeed is 1, count[c] is equal to the number of pairs of paths that start at c and do not share any edges.
In the case of the given path graph, count[c] is equal to the number of servers to the left of c multiplied by the servers to the right of c.
Example 2:
Input: edges = [[0,6,3],[6,5,3],[0,3,1],[3,2,7],[3,1,6],[3,4,2]], signalSpeed = 3
Output: [2,0,0,0,0,0,2]
Explanation: Through server 0, there are 2 pairs of connectable servers: (4, 5) and (4, 6).
Through server 6, there are 2 pairs of connectable servers: (4, 5) and (0, 5).
It can be shown that no two servers are connectable through servers other than 0 and 6.
Code
1
2
3