Count Pairs of Connectable Servers in a Weighted Tree Network
You are given an unrooted weighted tree with n vertices representing servers numbered from 0 to n - 1, an array edges where edges[i] = [ai, bi, weighti] represents a bidirectional edge between vertices ai and bi of weight weighti. You are also given an integer signalSpeed.
Two servers a and b are connectable through a server c if:
a < b,a != c, andb != c.- The distance from
ctoais divisible bysignalSpeed. - The distance from
ctobis divisible bysignalSpeed. - The path from
ctoband the path fromctoado not share any edges.
Return an integer array count of length n where count[i] is the number of server pairs that are connectable through the server i.
Example 1
Input
edges = [[0,1,1],[1,2,5],[2,3,13],[3,4,9],[4,5,2]], signalSpeed = 1Output
[0,4,6,6,4,0]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 given path graph, this is 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 = 3Output
[2,0,0,0,0,0,2]Through server 0, the connectable pairs are (4, 5) and (4, 6), and through server 6, the connectable pairs are (4, 5) and (0, 5); no other server has connectable pairs.
Constraints
- 2 <= n <= 1000
- edges.length == n - 1
- edges[i].length == 3
- 0 <= ai, bi < n
- edges[i] = [ai, bi, weighti]
- 1 <= weighti <= 10^6
- 1 <= signalSpeed <= 10^6
- The input is generated such that
edgesrepresents a valid tree.