3067. Count Pairs of Connectable Servers in a Weighted Tree Network
Description
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
c
toa
is divisible bysignalSpeed
. - The distance from
c
tob
is divisible bysignalSpeed
. - The path from
c
tob
and the path fromc
toa
do 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 = 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.
Constraints:
2 <= n <= 1000
edges.length == n - 1
edges[i].length == 3
0 <= ai, bi < n
edges[i] = [ai, bi, weighti]
1 <= weighti <= 106
1 <= signalSpeed <= 106
- The input is generated such that
edges
represents a valid tree.
Solutions
Solution 1: Enumeration + DFS
First, we construct an adjacency list g
based on the edges given in the problem, where g[a]
represents all the neighbor nodes of node a
and their corresponding edge weights.
Then, we can enumerate each node a
as the connecting intermediate node, and calculate the number of nodes t
that start from the neighbor node b
of a
and whose distance to node a
can be divided by signalSpeed
through depth-first search. Then, the number of connectable node pairs of node a
increases by s * t
, where s
represents the cumulative number of nodes that start from the neighbor node b
of a
and whose distance to node a
cannot be divided by signalSpeed
. Then we update s
to s + t
.
After enumerating all nodes a
, we can get the number of connectable node pairs for all nodes.
The time complexity is $O(n^2)$, and the space complexity is $O(n)$, where $n$ is the number of nodes.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
|