We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Count Pairs of Connectable Servers in a Weighted Tree Network

Difficulty: Medium

Problem 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] = [a_i, b_i, weight_i] represents a bidirectional edge between vertices a_i and b_i of weight weight_i. 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.
  • The distance from c to a is divisible by signalSpeed.
  • The distance from c to b is divisible by signalSpeed.
  • The path from 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.

Key Insights

  • The problem revolves around calculating valid pairs of servers based on specific distance divisibility conditions.
  • The tree structure allows for efficient traversal and distance calculation using Depth-First Search (DFS).
  • Each server can only connect to pairs of servers on its left and right without sharing any edges, which can be managed through subtree calculations.
  • The divisibility condition by signalSpeed adds an additional layer of filtering for the connectable pairs.

Space and Time Complexity

Time Complexity: O(n^2) in the worst case when checking all pairs for each server using DFS.
Space Complexity: O(n) due to the storage of graph representation and recursion stack.

Solution

To solve the problem, we can use a Depth-First Search (DFS) approach to traverse the tree and calculate distances from each server to its descendants. For each server, we will count the number of pairs of servers that can be connected based on the distance conditions.

  1. Build the tree using an adjacency list from the edges.
  2. For each server, perform a DFS to calculate the distances from that server to all other servers.
  3. Count the pairs of servers that meet the connectable conditions based on the calculated distances and the signalSpeed.

Code Solutions

def countPairs(edges, signalSpeed):
    from collections import defaultdict
    
    # Build the graph
    graph = defaultdict(list)
    for a, b, weight in edges:
        graph[a].append((b, weight))
        graph[b].append((a, weight))
        
    n = len(graph)
    count = [0] * n
    
    def dfs(node, parent, distance, distances):
        # Store the distance for the current node
        distances.append(distance)
        for neighbor, weight in graph[node]:
            if neighbor != parent:
                dfs(neighbor, node, distance + weight, distances)
                
    # Check each server as a potential connection point
    for c in range(n):
        distances = []
        dfs(c, -1, 0, distances)
        
        # Count pairs of distances divisible by signalSpeed
        valid_distances = [d for d in distances if d % signalSpeed == 0]
        count[c] = len(valid_distances) * (len(valid_distances) - 1) // 2
        
    return count
← Back to All Questions