Count pairs of connectable servers in a weighted tree network

Array Tree Depth-First Search

55.6% acceptance

Feb 25, 2026

238

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.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn count_pairs_of_connectable_servers(edges: Vec<Vec<i32>>, signal_speed: i32) -> Vec<i32> {
    let n = edges.len() + 1;
    let mut adj = vec![vec![]; n];
    for e in &edges {
      adj[e[0] as usize].push((e[1] as usize, e[2]));
      adj[e[1] as usize].push((e[0] as usize, e[2]));
    }
    let count_reachable = |root: usize, from: usize, dist: i64| -> i64 {
      let mut stack = vec![(root, from, dist)];
      let mut cnt = 0i64;
      while let Some((node, parent, d)) = stack.pop() {
        if d % signal_speed as i64 == 0 { cnt += 1; }
        for &(next, w) in &adj[node] {
          if next != parent { stack.push((next, node, d + w as i64)); }
        }
      }
      cnt
    };
    let mut res = vec![0i32; n];
    for c in 0..n {
      let mut _total = 0i64;
      let mut prev = 0i64;
      for &(neighbor, w) in &adj[c] {
        let cnt = count_reachable(neighbor, c, w as i64);
        res[c] += (prev * cnt) as i32;
        prev += cnt;
        _total += cnt;
      }
    }
    res
  }
}