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

1/**
2 * [3067] Count Pairs of Connectable Servers in a Weighted Tree Network
3 *
4 * 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.
5 * Two servers a and b are connectable through a server c if:
6 * 
7 * 	a < b, a != c and b != c.
8 * 	The distance from c to a is divisible by signalSpeed.
9 * 	The distance from c to b is divisible by signalSpeed.
10 * 	The path from c to b and the path from c to a do not share any edges.
11 * 
12 * Return an integer array count of length n where count[i] is the number of server pairs that are connectable through the server i.
13 *  
14 * <strong class="example">Example 1:
15 * <img alt="" src="https://assets.leetcode.com/uploads/2024/01/21/example22.png" style="width: 438px; height: 243px; padding: 10px; background: #fff; border-radius: .5rem;" />
16 * Input: edges = [[0,1,1],[1,2,5],[2,3,13],[3,4,9],[4,5,2]], signalSpeed = 1
17 * Output: [0,4,6,6,4,0]
18 * Explanation: Since signalSpeed is 1, count[c] is equal to the number of pairs of paths that start at c and do not share any edges.
19 * In the case of the given path graph, count[c] is equal to the number of servers to the left of c multiplied by the servers to the right of c.
20 * 
21 * <strong class="example">Example 2:
22 * <img alt="" src="https://assets.leetcode.com/uploads/2024/01/21/example11.png" style="width: 495px; height: 484px; padding: 10px; background: #fff; border-radius: .5rem;" />
23 * Input: edges = [[0,6,3],[6,5,3],[0,3,1],[3,2,7],[3,1,6],[3,4,2]], signalSpeed = 3
24 * Output: [2,0,0,0,0,0,2]
25 * Explanation: Through server 0, there are 2 pairs of connectable servers: (4, 5) and (4, 6).
26 * Through server 6, there are 2 pairs of connectable servers: (4, 5) and (0, 5).
27 * It can be shown that no two servers are connectable through servers other than 0 and 6.
28 * 
29 *  
30 * Constraints:
31 * 
32 * 	2 <= n <= 1000
33 * 	edges.length == n - 1
34 * 	edges[i].length == 3
35 * 	0 <= ai, bi < n
36 * 	edges[i] = [ai, bi, weighti]<!-- notionvc: a2623897-1bb1-4c07-84b6-917ffdcd83ec -->
37 * 	1 <= weighti <= 10^6
38 * 	1 <= signalSpeed <= 10^6
39 * 	The input is generated such that edges represents a valid tree.
40 * 
41 */
42pub struct Solution {}
43
44// problem: https://leetcode.com/problems/count-pairs-of-connectable-servers-in-a-weighted-tree-network/
45// discuss: https://leetcode.com/problems/count-pairs-of-connectable-servers-in-a-weighted-tree-network/discuss/?currentPage=1&orderBy=most_votes&query=
46
47// submission codes start here
48
49impl Solution {
50    pub fn count_pairs_of_connectable_servers(edges: Vec<Vec<i32>>, signal_speed: i32) -> Vec<i32> {
51        vec![]
52    }
53}
54
55// submission codes end
56
57#[cfg(test)]
58mod tests {
59    use super::*;
60
61    #[test]
62    fn test_3067() {
63    }
64}
65