Count Connectable Server Pairs Through Each Tree Vertex
Company: Rippling
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
# Count Connectable Server Pairs Through Each Tree Vertex
You are given a valid unrooted weighted tree with `n` servers numbered `0..n - 1`. Each row `edges[i] = [a_i,b_i,weight_i]` describes a bidirectional edge between servers `a_i` and `b_i` with the given weight. You are also given a positive integer `signalSpeed`.
For a fixed server `c`, a pair of servers `(a,b)` is connectable through `c` when all of the following hold:
- `a < b`, `a != c`, and `b != c`.
- The weighted distance from `c` to `a` is divisible by `signalSpeed`.
- The weighted distance from `c` to `b` is divisible by `signalSpeed`.
- The unique path from `c` to `a` and the unique path from `c` to `b` share no edges.
A weighted distance is the sum of edge weights along the path. Return an integer array `count` of length `n`, where `count[c]` is the number of pairs connectable through server `c`.
### Examples
**Example 1**
```text
Input: edges = [[0,1,2],[0,2,4],[0,3,3],[0,4,6]], signalSpeed = 2
Output: [3,0,0,0,0]
```
Through server `0`, the valid pairs are `(1,2)`, `(1,4)`, and `(2,4)`. Their individual distances from `0` are divisible by two and their paths use different edges. No pair is connectable through a leaf server.
**Example 2**
```text
Input: edges = [[0,1,2],[1,2,2],[2,3,1],[3,4,1]], signalSpeed = 2
Output: [0,2,2,0,0]
```
Through server `1`, the pairs are `(0,2)` and `(0,4)`. Through server `2`, they are `(0,4)` and `(1,4)`. Pair `(0,1)` is invalid through `2` even though both distances are divisible by two, because the paths share edge `(2,1)`. Through `3`, the paths to `2` and `4` each have distance one, so they fail the individual divisibility conditions.
### Constraints
- `2 <= n <= 1000`.
- `edges.length == n - 1`.
- `edges[i].length == 3`.
- `edges[i] = [a_i,b_i,weight_i]`, with `0 <= a_i,b_i < n`.
- `1 <= weight_i <= 10^6`.
- `1 <= signalSpeed <= 10^6`.
- The edges are guaranteed to form a valid tree.
### Clarifying Questions
- Can either endpoint equal the server through which the pair connects? No.
- May the two paths share the vertex `c`? Yes; they both begin there, but they may not share an edge.
- Is divisibility of the combined endpoint-to-endpoint distance enough? No; each distance from `c` must be divisible individually.
- Are `(a,b)` and `(b,a)` counted separately? No; `a < b` specifies one representation of each pair.
- In what order should the result be returned? By server label: the entry for `0`, then `1`, and so on.
### C++ Interface
```cpp
class Solution {
public:
vector<int> countPairsOfConnectableServers(vector<vector<int>>& edges, int signalSpeed) {
}
};
```
### Reasoning Checkpoints
- Enforce both individual distance tests and the edge-disjoint path requirement.
- Exclude the connecting server from pair endpoints and count each pair once.
- Justify the per-server counts, numeric bounds, and resource costs for a valid weighted tree.
```hint Separate the paths by their first edge
Fix a connecting server c. Removing c separates the tree into components, one per neighbor. Count eligible endpoints in each component, then combine endpoints from different components without counting a pair twice.
```
Overview: Count server pairs connectable through each vertex of a weighted tree, requiring individual distance divisibility and paths that share no edges.