Total Sum of Interaction Cost in Tree Groups
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.
You are also given an integer array group of length n, where group[i] denotes the group label assigned to node i.
- Two nodes
uandvare considered part of the same group ifgroup[u] == group[v]. - The interaction cost between
uandvis defined as the number of edges on the unique path connecting them in the tree.
Return an integer denoting the sum of interaction costs over all unordered pairs (u, v) with u != v such that group[u] == group[v].
Example 1
Input
n = 3, edges = [[0,1],[1,2]], group = [1,1,1]Output
4All nodes belong to group 1, and the pairwise interaction costs are 1, 1, and 2, for a total of 4.
Example 2
Input
n = 3, edges = [[0,1],[1,2]], group = [3,2,3]Output
2Nodes 0 and 2 belong to group 3 and have interaction cost 2, while node 1 forms no valid pair.
Constraints
- 1 <= n <= 10^5
- edges.length == n - 1
- edges[i] = [ui, vi]
- 0 <= ui, vi <= n - 1
- group.length == n
- 1 <= group[i] <= 20
- The input is generated such that edges represents a valid tree.