3067. Count Pairs of Connectable Servers in a Weighted Tree Network
Asked at Rippling
Difficulty
Medium
Time
O(n^2)
Space
O(n)
Pattern
Array
Companies
1
Problem
You are given an unrooted weighted tree with n servers, numbered 0 to n-1. Each edge [a, b, w] connects server a and server b and has a positive weight w. You are also given an integer signalSpeed.
Two servers a and b are connectable through a third server c when all of these hold: a < b, neither a nor b equals c, the distance from c to a is divisible by signalSpeed, the distance from c to b is divisible by signalSpeed, and the two paths c → a and c → b share no edges. The last rule means a and b must lie in two different branches hanging off c.
Return an array count of length n, where count[i] is the number of connectable pairs through server i.
A useful way to think about it: for a fixed center c, cut c out of the tree. The tree splits into one separate piece per neighbor of c. A valid pair must take one server from one piece and the other server from a different piece, and both distances measured from c must be multiples of signalSpeed.
Pairs must come from different branches
Constraints
- ●
2 <= n <= 1000 - ●
edges.length == n - 1 - ●
edges[i].length == 3 - ●
0 <= ai, bi < n - ●
1 <= weighti <= 10^6 - ●
1 <= signalSpeed <= 10^6 - ●
The input is generated such that edges represents a valid tree.
Examples
edges = [[0,1,1],[1,2,5],[2,3,13],[3,4,9],[4,5,2]], signalSpeed = 1[0,4,6,6,4,0]edges = [[0,6,3],[6,5,3],[0,3,1],[3,2,7],[3,1,6],[3,4,2]], signalSpeed = 3[2,0,0,0,0,0,2]edges = [[0,1,3],[1,2,1],[1,3,4]], signalSpeed = 2[0,1,0,0]Asked At
1 companies| Company | Difficulty | |
|---|---|---|
| Rippling | Medium | View all Rippling questions → |
How to Think About It
For each center server i, remove i to get a forest of subtrees. For each subtree, collect the distances from i to every node in that subtree, modulo signalSpeed.
Two nodes a and b are connectable through i if they are in different subtrees (different first-edge branches from i) and (dist(i,a) + dist(i,b)) % signalSpeed == 0.
Efficient counting: for each subtree, maintain a frequency array of (distance % signalSpeed). For each new subtree, count pairs with already-seen subtrees using the complement: seen[(signalSpeed - r) % signalSpeed] gives the count of nodes in previous subtrees where adding this node makes the sum divisible.
Algorithm for each center: DFS into each neighbor branch to collect distance mods. For each branch, count cross-branch pairs using the complement formula, then merge the branch into the seen set.
Total complexity: O(n^2) because for each of n centers, we do O(n) work (DFS + pair counting). This is acceptable since n <= 1000.
Optimal Approach
Step 1: Build adjacency list for the tree.
Step 2: For each server i (center):
a. For each neighbor j of i, DFS through j to collect distances from i. Build a frequency array of (distance % signalSpeed).
b. For each new subtree, count cross-branch pairs: for each remainder r in the subtree, add seen[(signalSpeed - r) % signalSpeed] to the answer.
c. Merge the subtree frequencies into the running seen set.
Step 3: Return the answers array.
Walkthrough for n=4, edges=[[0,1,3],[1,2,1],[1,3,4]], signalSpeed=2:
- Center 1: DFS into 0 (dist=3, mod=1), 2 (dist=1, mod=1), 3 (dist=4, mod=0).
- Subtree 0: mod 1 count=1. Pairs with seen: seen[1]=0. Total=0. Merge: seen[1]=1.
- Subtree 2: mod 1 count=1. Pairs with seen: seen[1]=1. Total+=1. Merge: seen[1]=2.
- Subtree 3: mod 0 count=1. Pairs with seen: seen[0]=0. Total+=0. Merge: seen[0]=1.
- Answer[1] = 1.
- Center 0: one subtree (via 1). No cross-branch pairs. Answer[0] = 0.
- Similarly for centers 2 and 3: answer = [0,1,0,0].
Time: O(n^2) - for each center, DFS is O(n) and pair counting is O(n). Space: O(n) for DFS recursion and frequency arrays.
Count per branch, then merge
What Trips People Up in Real Interviews
Counting pairs within the same subtree. Connectable pairs must be in DIFFERENT subtrees (different first-edge branches from i).
Forgetting that the tree is weighted. Distances are accumulated edge weights, not just hop counts. Use the actual weight when computing dist(i, child).
Wrong modular arithmetic. (dist_a + dist_b) % s == 0 means dist_a % s and dist_b % s are complements: (r_a + r_b) % s == 0.
Missing that the result is an array, not a single number. Each server i gets its own count of connectable pairs.
Double-counting pairs. Each pair (a,b) is counted once when processing center i. Do not count (a,b) and (b,a) separately.
Solution Code
O(n^2) timeclass Solution:
def countPairsOfConnectableServers(self, edges, signalSpeed):
n = len(edges) + 1
g = [[] for _ in range(n)]
for a, b, w in edges:
g[a].append((b, w))
g[b].append((a, w))
def branch_counts(center):
counts = []
for v, w in g[center]:
cnt = [0] * signalSpeed
stack = [(v, center, w)]
while stack:
u, p, d = stack.pop()
cnt[d % signalSpeed] += 1
for nb, ww in g[u]:
if nb != p:
stack.append((nb, u, d + ww))
counts.append(cnt)
return counts
ans = [0] * n
for c in range(n):
seen = [0] * signalSpeed
for cnt in branch_counts(c):
for r in range(signalSpeed):
ans[c] += cnt[r] * seen[(signalSpeed - r) % signalSpeed]
for r in range(signalSpeed):
seen[r] += cnt[r]
return ansFrequently Asked Questions
What is the Count Pairs of Connectable Servers in a Weighted Tree Network problem?
Given a weighted tree with n servers (0 to n-1) and edges [a, b, weight], count for each server i the number of pairs (a, b) where a and b are in different branches of i, and the combined distance from i to a and i to b is divisible by signalSpeed.
How do you solve Count Pairs of Connectable Servers in a Weighted Tree Network?
The optimal approach runs in O(n^2) time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Count Pairs of Connectable Servers in a Weighted Tree Network?
Count Pairs of Connectable Servers in a Weighted Tree Network is asked at Rippling. It is a medium difficulty problem.
What are common mistakes on Count Pairs of Connectable Servers in a Weighted Tree Network?
- Counting pairs within the same subtree. Connectable pairs must be in DIFFERENT subtrees (different first-edge branches from i).
- Forgetting that the tree is weighted. Distances are accumulated edge weights, not just hop counts. Use the actual weight when computing dist(i, child).
- Wrong modular arithmetic. (dist_a + dist_b) % s == 0 means dist_a % s and dist_b % s are complements: (r_a + r_b) % s == 0.
- Missing that the result is an array, not a single number. Each server i gets its own count of connectable pairs.
- Double-counting pairs. Each pair (a,b) is counted once when processing center i. Do not count (a,b) and (b,a) separately.