Practice/NVIDIA/Leetcode 3067. Count Pairs of Connectable Servers in a Weighted Tree Network

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

CodingMust

Problem

You are given a tree network of servers represented by n nodes numbered from 0 to n-1. The tree is defined by an array edges where each element edges[i] = [ui, vi, weighti] represents a bidirectional connection between servers ui and vi with a signal transmission cost of weighti.

A signal can propagate between two servers with a certain efficiency. For a given signalSpeed, two servers can establish an efficient connection if the total transmission cost (sum of edge weights) along their path is divisible by signalSpeed.

For each server c in the network, you need to count the number of unordered pairs of distinct servers (a, b) that satisfy:

• Neither a nor b equals c
• The path from c to a has a total cost divisible by signalSpeed
• The path from c to b has a total cost divisible by signalSpeed
• The paths from c to a and from c to b start by going through different edges connected to c (they branch into different subtrees)

Return an array where the i-th element represents the count of such valid pairs for server i.

Requirements

1. Build the tree structure from the given edges
2. For each node, explore all subtrees connected to it
3. Count nodes in each subtree whose distance from the center node is divisible by signalSpeed
4. Calculate pair counts by multiplying counts from different subtrees
5. Return an array with pair counts for each node

Constraints

• 2 <= n <= 1000
• edges.length == n - 1
• edges[i].length == 3
• 0 <= ui, vi < n
• edges represents a valid tree
• 1 <= weighti <= 10^6
• 1 <= signalSpeed <= 10^6

Examples

Example 1:

Input: edges = [[0,1,1], [1,2,5], [1,3,13]], signalSpeed = 1 Output: [0, 4, 0, 0] Explanation: Since signalSpeed = 1, all distances are divisible by 1. For node 1 (center): It connects to nodes 0, 2, and 3 through different edges. All pairs (0,2), (0,3), (2,3) would satisfy the conditions if they're in different subtrees. Node 0 is in one subtree, node 2 in another, node 3 leads to another subtree. Valid pairs through node 1: (0,2), (0,3) = 2 pairs... (calculation depends on tree structure)

Example 2:

Input: edges = [[0,1,2], [1,2,3]], signalSpeed = 5 Output: [0, 0, 0] Explanation: No distances (2, 3, or 5) are divisible by 5 except when considering the full path 0-1-2 which equals 5. However, for any center node, we cannot find two distinct nodes in different branches both at distances divisible by 5.

Example 3:

Input: edges = [[0,1,2], [0,2,2], [0,3,4]], signalSpeed = 2 Output: [3, 0, 0, 0] Explanation: For node 0: distances to nodes 1, 2, and 3 are 2, 2, and 4 respectively. All are divisible by 2. Each node (1, 2, 3) is in a different subtree from node 0. Valid pairs: (1,2), (1,3), (2,3) = 3 pairs.