3067. Count Pairs of Connectable Servers in a Weighted Tree Network LeetCode Solution

Last updated: March 6, 2025

In this guide, you will get 3067. Count Pairs of Connectable Servers in a Weighted Tree Network LeetCode Solution with the best time and space complexity. The solution to Count Pairs of Connectable Servers in a Weighted Tree Network problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

  1. Problem Statement
  2. Complexity Analysis
  3. Count Pairs of Connectable Servers in a Weighted Tree Network solution in C++
  4. Count Pairs of Connectable Servers in a Weighted Tree Network solution in Java
  5. Count Pairs of Connectable Servers in a Weighted Tree Network solution in Python
  6. Additional Resources
3067. Count Pairs of Connectable Servers in a Weighted Tree Network LeetCode Solution image

Problem Statement of Count Pairs of Connectable Servers in a Weighted Tree Network

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.
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.

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.

Complexity Analysis

  • Time Complexity: O(n^2)
  • Space Complexity: O(n)

3067. Count Pairs of Connectable Servers in a Weighted Tree Network LeetCode Solution in C++

class Solution {
 public:
  vector<int> countPairsOfConnectableServers(vector<vector<int>>& edges,
                                             int signalSpeed) {
    const int n = edges.size() + 1;
    vector<int> ans;
    vector<vector<pair<int, int>>> tree(n);

    for (const vector<int>& edge : edges) {
      const int u = edge[0];
      const int v = edge[1];
      const int w = edge[2];
      tree[u].emplace_back(v, w);
      tree[v].emplace_back(u, w);
    }

    for (int i = 0; i < n; ++i)
      ans.push_back(connectablePairsRootedAt(tree, i, signalSpeed));

    return ans;
  }

 private:
  // Returns the number of server pairs that are connectable through the server
  // `u`.
  int connectablePairsRootedAt(const vector<vector<pair<int, int>>>& tree,
                               int u, int signalSpeed) {
    int pairs = 0;
    int count = 0;
    for (const auto& [v, w] : tree[u]) {
      const int childCount = dfs(tree, v, u, w, signalSpeed);
      pairs += count * childCount;
      count += childCount;
    }
    return pairs;
  }

  // Returns the number of servers that are connectable throught the server `u`
  // (dist % signalSpeed == 0).
  int dfs(const vector<vector<pair<int, int>>>& tree, int u, int prev, int dist,
          int signalSpeed) {
    int count = 0;
    for (const auto& [v, w] : tree[u])
      if (v != prev)
        count += dfs(tree, v, u, dist + w, signalSpeed);
    return (dist % signalSpeed == 0 ? 1 : 0) + count;
  }
};
/* code provided by PROGIEZ */

3067. Count Pairs of Connectable Servers in a Weighted Tree Network LeetCode Solution in Java

class Solution {
  public int[] countPairsOfConnectableServers(int[][] edges, int signalSpeed) {
    final int n = edges.length + 1;
    int[] ans = new int[n];
    List<Pair<Integer, Integer>>[] graph = new List[n];

    for (int i = 0; i < n; i++)
      graph[i] = new ArrayList<>();

    for (final int[] edge : edges) {
      final int u = edge[0];
      final int v = edge[1];
      final int w = edge[2];
      graph[u].add(new Pair<>(v, w));
      graph[v].add(new Pair<>(u, w));
    }

    for (int i = 0; i < n; ++i)
      ans[i] = connectablePairsRootedAt(graph, i, signalSpeed);

    return ans;
  }

  // Returns the number of server pairs that are connectable through the server
  // `u`.
  private int connectablePairsRootedAt(List<Pair<Integer, Integer>>[] graph, int u,
                                       int signalSpeed) {
    int pairs = 0;
    int count = 0;
    for (Pair<Integer, Integer> pair : graph[u]) {
      final int v = pair.getKey();
      final int w = pair.getValue();
      final int childCount = dfs(graph, v, u, w, signalSpeed);
      pairs += count * childCount;
      count += childCount;
    }
    return pairs;
  }

  // Returns the number of servers that are connectable throught the server `u`
  // (dist % signalSpeed == 0).
  private int dfs(List<Pair<Integer, Integer>>[] graph, int u, int prev, int dist,
                  int signalSpeed) {
    int count = 0;
    for (Pair<Integer, Integer> pair : graph[u]) {
      final int v = pair.getKey();
      final int w = pair.getValue();
      if (v != prev)
        count += dfs(graph, v, u, dist + w, signalSpeed);
    }
    return (dist % signalSpeed == 0 ? 1 : 0) + count;
  }
}
// code provided by PROGIEZ

3067. Count Pairs of Connectable Servers in a Weighted Tree Network LeetCode Solution in Python

class Solution:
  def countPairsOfConnectableServers(
      self,
      edges: list[list[int]],
      signalSpeed: int,
  ) -> list[int]:
    n = len(edges) + 1
    tree = [[] for _ in range(n)]

    for u, v, w in edges:
      tree[u].append((v, w))
      tree[v].append((u, w))

    def connectablePairsRootedAt(u: int) -> int:
      pairs = 0
      count = 0
      for v, w in tree[u]:
        childCount = dfs(v, u, w)
        pairs += count * childCount
        count += childCount
      return pairs

    def dfs(u: int, prev: int, dist: int) -> int:
      return (int(dist % signalSpeed == 0) +
              sum(dfs(v, u, dist + w)
              for v, w in tree[u]
              if v != prev))

    return [connectablePairsRootedAt(i) for i in range(n)]
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.