### 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)

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

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;
}
};
```