Count Pairs of Connectable Servers in a Weighted Tree Network - Video Solutions

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.