3786. Total Sum of Interaction Cost in Tree Groups Hard

1/**
2 * [3786] Total Sum of Interaction Cost in Tree Groups
3 *
4 * You are given an integer n and an undirected tree with n nodes numbered from 0 to n - 1. This is represented by a 2D array edges of length n - 1, where edges[i] = [ui, vi] indicates an undirected edge between nodes ui and vi.
5 * You are also given an integer array group of length n, where group[i] denotes the group label assigned to node i.
6 * 
7 * 	Two nodes u and v are considered part of the same group if group[u] == group[v].
8 * 	The interaction cost between u and v is defined as the number of edges on the unique path connecting them in the tree.
9 * 
10 * Return an integer denoting the sum of interaction costs over all unordered pairs (u, v) with u != v such that group[u] == group[v].
11 *  
12 * <strong class="example">Example 1:
13 * <div class="example-block">
14 * Input: <span class="example-io">n = 3, edges = [[0,1],[1,2]], group = [1,1,1]</span>
15 * Output: <span class="example-io">4</span>
16 * Explanation:
17 * <strong class="example"><img alt="" src="https://assets.leetcode.com/uploads/2025/09/24/screenshot-2025-09-24-at-50538-pm.png" style="width: 250px; height: 57px;" />
18 * All nodes belong to group 1. The interaction costs between the pairs of nodes are:
19 * 
20 * 	Nodes (0, 1): 1
21 * 	Nodes (1, 2): 1
22 * 	Nodes (0, 2): 2
23 * 
24 * Thus, the total interaction cost is 1 + 1 + 2 = 4.
25 * </div>
26 * <strong class="example">Example 2:
27 * <div class="example-block">
28 * Input: <span class="example-io">n = 3, edges = [[0,1],[1,2]], group = [3,2,3]</span>
29 * Output: <span class="example-io">2</span>
30 * Explanation:
31 * 
32 * 	Nodes 0 and 2 belong to group 3. The interaction cost between this pair is 2.
33 * 	Node 1 belongs to a different group and forms no valid pair. Therefore, the total interaction cost is 2.
34 * </div>
35 * <strong class="example">Example 3:
36 * <div class="example-block">
37 * Input: <span class="example-io">n = 4, edges = [[0,1],[0,2],[0,3]], group = [1,1,4,4]</span>
38 * Output: <span class="example-io">3</span>
39 * Explanation:
40 * <img src="https://assets.leetcode.com/uploads/2025/09/24/screenshot-2025-09-24-at-51312-pm.png" style="width: 200px; height: 146px;" />
41 * Nodes belonging to the same groups and their interaction costs are:
42 * 
43 * 	Group 1: Nodes (0, 1): 1
44 * 	Group 4: Nodes (2, 3): 2
45 * 
46 * Thus, the total interaction cost is 1 + 2 = 3.
47 * </div>
48 * <strong class="example">Example 4:
49 * <div class="example-block">
50 * Input: <span class="example-io">n = 2, edges = [[0,1]], group = [9,8]</span>
51 * Output: <span class="example-io">0</span>
52 * Explanation:
53 * All nodes belong to different groups and there are no valid pairs. Therefore, the total interaction cost is 0.
54 * </div>
55 *  
56 * Constraints:
57 * 
58 * 	1 <= n <= 10^5
59 * 	edges.length == n - 1
60 * 	edges[i] = [ui, vi]
61 * 	0 <= ui, vi <= n - 1
62 * 	group.length == n
63 * 	1 <= group[i] <= 20
64 * 	The input is generated such that edges represents a valid tree.
65 * 
66 */
67pub struct Solution {}
68
69// problem: https://leetcode.com/problems/total-sum-of-interaction-cost-in-tree-groups/
70// discuss: https://leetcode.com/problems/total-sum-of-interaction-cost-in-tree-groups/discuss/?currentPage=1&orderBy=most_votes&query=
71
72// submission codes start here
73
74impl Solution {
75    pub fn interaction_costs(n: i32, edges: Vec<Vec<i32>>, group: Vec<i32>) -> i64 {
76        
77    }
78}
79
80// submission codes end
81
82#[cfg(test)]
83mod tests {
84    use super::*;
85
86    #[test]
87    fn test_3786() {
88    }
89}
90