Tap here to switch tabs
Problem
Submissions

Problem: Total Sum of Interaction Cost in Tree Groups

Try to solve the Total Sum of Interaction Cost in Tree Groups problem.

Statement

You are given an undirected tree with nn nodes labeled from 00 to n−1n - 1, represented by a 22D integer array edges of length n−1n - 1, where edges[i] =[ui,vi]= [u_i, v_i] denotes an undirected edge between nodes uiu_i and viv_i.

You are also given an integer array group of length nn, where group[i] denotes the group assigned to node i.

The interaction cost between a pair of distinct nodes u and v (u<vu < v) that belong to the same group (that is, group[u] == group[v]) is defined as the number of edges on the unique path between them.

Return the total sum of interaction costs across all pairs of distinct nodes that belong to the same group.

Constraints:

  • 1≤1 \leq n ≤105\leq 10^5

  • edges.length =n−1= n - 1

  • edges[i] =[ui,vi]= [u_i, v_i]

  • 0≤ui,vi≤n−10 \leq u_i, v_i \leq n - 1

  • group.length =n= n

  • 1≤1 \leq group[i] ≤20\leq 20

  • The input is generated such that edges represents a valid tree.

⋮
Tap here to switch tabs
Problem
Submissions

Problem: Total Sum of Interaction Cost in Tree Groups

Try to solve the Total Sum of Interaction Cost in Tree Groups problem.

Statement

You are given an undirected tree with nn nodes labeled from 00 to n−1n - 1, represented by a 22D integer array edges of length n−1n - 1, where edges[i] =[ui,vi]= [u_i, v_i] denotes an undirected edge between nodes uiu_i and viv_i.

You are also given an integer array group of length nn, where group[i] denotes the group assigned to node i.

The interaction cost between a pair of distinct nodes u and v (u<vu < v) that belong to the same group (that is, group[u] == group[v]) is defined as the number of edges on the unique path between them.

Return the total sum of interaction costs across all pairs of distinct nodes that belong to the same group.

Constraints:

  • 1≤1 \leq n ≤105\leq 10^5

  • edges.length =n−1= n - 1

  • edges[i] =[ui,vi]= [u_i, v_i]

  • 0≤ui,vi≤n−10 \leq u_i, v_i \leq n - 1

  • group.length =n= n

  • 1≤1 \leq group[i] ≤20\leq 20

  • The input is generated such that edges represents a valid tree.