Skip to content

4018. Total Sum of Interaction Cost in Tree Groups II πŸ”’

Description

You are given an integer n and an undirected tree rooted at node 0 with n nodes numbered from 0 to n - 1. The tree is represented by a 2D integer 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 u and v belong to the same group if and only if group[u] == group[v].
  • The interaction cost between two nodes is the shortest distance between them in the tree.

Return the sum of interaction costs over all pairs of node indices (u, v) such that 0 <= u < v < n and group[u] == group[v].

The shortest distance between two nodes is the number of edges on the unique path connecting them in the tree.

Β 

Example 1:

Input: n = 3, edges = [[0,1],[1,2]], group = [1,1,1]

Output: 4

Explanation:

All nodes belong to group 1. The interaction costs between the pairs of nodes are:

  • Nodes [0, 1]: 1
  • Nodes [1, 2]: 1
  • Nodes [0, 2]: 2

Thus, the total interaction cost is 1 + 1 + 2 = 4.

Example 2:

Input: n = 3, edges = [[0,1],[1,2]], group = [3,2,3]

Output: 2

Explanation:

  • Nodes 0 and 2 belong to group 3. The interaction cost between this pair is 2.
  • Node 1 belongs to a different group and forms no valid pair. Therefore, the total interaction cost is 2.

Example 3:

Input: n = 4, edges = [[0,1],[0,2],[0,3]], group = [1,1,4,4]

Output: 3

Explanation:

​​​​​​​​​​​​​​

Nodes belonging to the same groups and their interaction costs are:

  • Group 1: Nodes [0, 1]: 1
  • Group 4: Nodes [2, 3]: 2

Thus, the total interaction cost is 1 + 2 = 3.

Example 4:

Input: n = 2, edges = [[0,1]], group = [1,2]

Output: 0

Explanation:

All nodes belong to different groups and there are no valid pairs. Therefore, the total interaction cost is 0.

Β 

Constraints:

  • 1 <= n <= 105
  • edges.length == n - 1
  • edges[i] = [ui, vi]
  • 0 <= ui, vi <= n - 1
  • group.length == n
  • 1 <= group[i] <= n
  • The input is generated such that edges represents a valid tree.

Solutions

Solution 1

1


1


1


1

Comments