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 and b != c.c to a is divisible by signalSpeed.c to b is divisible by signalSpeed.c to b and the path from c to a 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 <= 1000edges.length == n - 1edges[i].length == 30 <= ai, bi < nedges[i] = [ai, bi, weighti]1 <= weighti <= 1061 <= signalSpeed <= 106edges represents a valid tree.Problem Overview: You are given a weighted tree representing a network of servers. For every server acting as a signal source, count pairs of other servers whose shortest path distances from that source are divisible by signalSpeed and lie in different branches of the tree. The goal is to compute how many such connectable pairs exist for every node.
Approach 1: DFS with Path Tracking (O(n²) time, O(n) space)
Treat each server as the root of the signal. From that root, run DFS into each neighboring branch and track cumulative path distance. For every visited node, check distance % signalSpeed == 0. Maintain a count of valid nodes discovered in each branch. Since connectable pairs must come from different branches, combine counts using multiplication: if branch A has a valid nodes and branch B has b, they contribute a * b pairs. Repeat this process for every node as the source. The algorithm relies on adjacency lists and recursive traversal of the tree. Time complexity is O(n²) because a DFS runs from each node, while space complexity is O(n) for recursion and distance tracking.
Approach 2: Centroid Decomposition with DFS (O(n log n) time, O(n) space)
Centroid decomposition reduces repeated traversal in large trees. Instead of running full DFS from every node, repeatedly split the tree around a centroid node that balances subtree sizes. For each centroid, run DFS through its subtrees and compute path distances modulo signalSpeed. Track how many nodes satisfy the divisibility condition and merge counts across subtrees to form valid pairs. Because each decomposition level processes disjoint subtrees and the tree height shrinks logarithmically, the overall complexity becomes O(n log n). This method combines depth-first search with divide‑and‑conquer on the tree structure.
Recommended for interviews: The DFS with path tracking approach is usually expected first because it clearly models the branching constraint and shows strong understanding of tree traversal. Once that works, discussing centroid decomposition demonstrates advanced optimization skills and awareness of scalable tree-processing techniques.
Utilize Depth First Search (DFS) to calculate the distance from each node to the root (or any random starting point). As you process each node, you can recursively determine all paths and check if two nodes can connect through a node. This can be achieved by understanding there's always a unique path in the tree between any two nodes. Thoroughly traverse each possible connection and check divisibility of distances to establish potential connectivity.
This solution implemented in Python leverages DFS to explore each node and gather all possible paths from each vertex. By traversing each path and calculating distances incrementally, the solution checks divisibility conditions for potential connectivity. This derives from the uniqueness of paths in a tree structure and allows for efficient pair identification.
Time Complexity: O(n^2) due to the nested exploration and construction of paths; Space Complexity: O(n) given the storage of path lengths during DFS operations.
Root the tree at a given node and utilize centroid decomposition to efficiently evaluate connectability for pairs across the network. With the tree naturally serving as a connected acyclic graph, begin by identifying paths rooted at the center and then iterate through divide-and-conquer methodology for simplification of remaining connections. Ensure that calculated distances maintain divisibility with the signal speed requirement, enabling the pair connection when weighted paths comply.
The Java solution engages a method of centroid decomposition combined with BFS for tree traversal, switching out DFS for iterative structures as a choice in this language. With efficient pair calculation using combinatorics, the utility of powers checks the math behind potential paths in complement with signal speed divisibility. Graph nodes are built similar to adjacency lists, facilitating BFS traversal and dynamic changes in calculation of connectable pairs.
Java
JavaScript
Time Complexity: O(n^2), as we effectively recompute paths and check every possibility for connectivity, with space overhead of O(n) for node stats to keep track of visited nodes and edge weights.
| Approach | Complexity |
|---|---|
| DFS with Path Tracking | Time Complexity: O(n^2) due to the nested exploration and construction of paths; Space Complexity: O(n) given the storage of path lengths during DFS operations. |
| Centroid Decomposition with DFS | Time Complexity: O(n^2), as we effectively recompute paths and check every possibility for connectivity, with space overhead of O(n) for node stats to keep track of visited nodes and edge weights. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| DFS with Path Tracking | O(n²) | O(n) | Best for interviews and moderate constraints where running DFS from each node is acceptable |
| Centroid Decomposition with DFS | O(n log n) | O(n) | Large trees where repeated full traversals are expensive; demonstrates advanced tree optimization |
3067. Count Pairs of Connectable Servers in a Weighted Tree Network | Graph | DFS | Math • Aryan Mittal • 4,615 views views
Watch 9 more video solutions →Practice Count Pairs of Connectable Servers in a Weighted Tree Network with our built-in code editor and test cases.
Practice on FleetCode