Total Sum of Interaction Cost in Tree Groups - Solution & Explanation

Problem Overview: You are given nodes organized as a tree and an array describing which group each node belongs to. The interaction cost between two nodes is the distance along the tree. The goal is to compute the total cost across all pairs of nodes that belong to the same group.

Approach 1: Pairwise Distance with LCA (Brute Force) (Time: O(k^2 log n), Space: O(n))

Group nodes by their group id using a hash map. For each group, iterate over every pair of nodes and compute their tree distance using a Lowest Common Ancestor structure such as binary lifting. The distance formula is dist(u,v) = depth[u] + depth[v] - 2 * depth[lca(u,v)]. This approach is easy to implement after building the LCA preprocessing in O(n log n). The downside is the quadratic pair iteration inside each group, which becomes too slow when a group contains many nodes.

Approach 2: DFS Subtree Aggregation (Optimal) (Time: O(n log n), Space: O(n))

Use a depth-first traversal of the tree and maintain frequency maps that track how many nodes of each group appear inside the current subtree. When processing an edge between a node and its child, the edge contributes to the distance between any pair of nodes whose path crosses that edge. If a group has a nodes in the child subtree and b nodes outside it, that edge contributes a * b to the total distance for that group.

During DFS, each node returns a map {group -> count} representing how many nodes of each group exist in its subtree. Merge child maps into the parent map using the small-to-large merging technique to keep the complexity under control. While merging, update the global interaction cost using the edge contribution formula. Small-to-large ensures each element moves only O(log n) times, giving overall O(n log n) time.

This method leverages the structure of a tree and processes every edge exactly once while maintaining group counts discovered via depth-first search. The grouping information originates from the input array, but the heavy work happens during the DFS aggregation.

Recommended for interviews: The DFS subtree aggregation approach is the expected solution. Interviewers want to see whether you can translate pairwise distance calculations into edge contributions on a tree. Starting with the brute-force pair approach shows understanding of the distance formula, but optimizing with DFS aggregation demonstrates strong tree and counting techniques.