3067. Counting the number of connectable server pairs in a weighted tree network.

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

You are given a weighted tree without a root. The tree has a total of $n$ nodes, representing $n$ servers, numbered from $0$ to $n - 1$ . You are also given an array $edges$ , where $edges[i] = [a_i, b_i, weight_i]$ represents a bidirectional edge between nodes $a_i$ and $b_i$ with a weight of $weight_i$ . Additionally, you are given an integer $signalSpeed$ .

If two servers $a$ , $b$ , and $c$ satisfy the following conditions, then we consider servers $a$ and $b$ to be connectable through server $c$ :

$a < b$ , $a\ne c$ , and $b\ne 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$ does not share any common edges with the path from $c$ to $a$ .

Return an integer array $count$ of length $n$ , where $count[i]$ represents the number of server pairs that are connectable through 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 equal to 1, count[c] is equal to the number of pairs of paths starting from c and having no common edges.
In the input graph, count[c] is equal to the product of the number of servers to the left of c and the number of 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: There are 2 connectable server pairs (4, 5) and (4, 6) through server 0.
There are 2 connectable server pairs (4, 5) and (0, 5) through server 6.
All other server pairs can only be connected through server 0 or 6, so the number of connectable server pairs for the other servers is 0.

Note:

$2 <= n <= 1000$
$edges.length == n - 1$
$edges[i].length == 3$
$0 <= a_i, b_i < n$
$edges[i] = [a_i, b_i, weight_i]$
$1 <= weight_i <= 10^6$
$1 <= signalSpeed <= 10^6$
The input ensures that the $edges$ form a valid tree.

Root Enumeration#

$a < b$ , $a \ne c$ , and $b \ne 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$ does not share any common edges with the path from $c$ to $a$ .

From the conditions for connectivity, we can obtain the following information:

The positions of $a$ and $b$ can be swapped, as long as there is a difference between them. (This can also be understood as preventing duplicates)

3067. Count Pairs of Connectable Servers in a Weighted Tree Network_1

$c$ is a node that divides the undirected acyclic graph into two parts, so that the path from $c$ to $a$ and the path from $c$ to $b$ do not share any common edges.

3067. Count Pairs of Connectable Servers in a Weighted Tree Network_2

Analyze the following cases:

Traverse to subtree 1:

Traverse to subtree 2:

Traverse to subtree 3:

The sum of the results that satisfy the conditions for each traversal is the number of connectable node pairs for the current root node.

Code implementation:

class Solution {
public:
    vector<int> countPairsOfConnectableServers(vector<vector<int>> &edges, int signalSpeed) {
        int n = edges.size() + 1; // There is one less edge than the number of nodes
        // {root, [<child1, cost1>, <child2, cost2>, ..., <childn, costn>]}
        vector<vector<pair<int, int>>> graph(n);

        for (const auto &edge : edges) {
            graph[edge[0]].push_back({edge[1], edge[2]});
            graph[edge[1]].push_back({edge[1], edge[2]});
        }

        /// @brief 
        /// @param root The root node, this parameter is passed in to prevent the root node of the subtree from going to this node
        /// @param child Child node
        /// @param remainder The distance from the root node to the child node
        /// @return Returns the number of nodes in the subtree rooted at root, which satisfies that the path to reach it can be divided by signalSpeed
        function<int(int, int, int)> dfs = [&](int root, int child, int remainder) -> int {
            int res = 0;
            if (remainder == 0) {
                ++res;
            }

            // Traverse all subtrees of the child node
            for (const auto &[j, cost] : graph[child]) {
                // Exclude the root node path
                if (j != root) {
                    res += dfs(child, j, (remainder + cost) % signalSpeed);
                }
            }
            return res;
        };

        vector<int> res(n);

        // Traverse the root nodes
        for (int i = 0; i < n; ++i) {
            int pre = 0; // Count the number of connectable pairs of the subtree of the root node

            // Traverse all subtrees of the root node
            for (auto &[j, cost] : graph[i]) {
                // The number of nodes that satisfy the current subtree
                int cnt = dfs(i, j, cost % signalSpeed);
                res[i] += pre * cnt;
                pre += cnt;
            }
        }
        return res;
    }
};