Problem Description

You are given a binary tree with n nodes labeled from 0 to n - 1, where node 0 is the root. The tree structure is represented by a 0-indexed array parents, where parents[i] indicates the parent of node i. Since node 0 is the root, parents[0] == -1.

The task is to calculate a score for each node in the tree. To find the score of a particular node:

1. Imagine removing that node and all edges connected to it from the tree
2. This removal will split the tree into one or more non-empty subtrees
3. The score of the node equals the product of the sizes of all these resulting subtrees

For example, if removing a node creates three subtrees with sizes 2, 3, and 4 nodes respectively, the score of that node would be 2 × 3 × 4 = 24.

Your goal is to find how many nodes have the highest score among all nodes in the tree.

Key Points:

• When a node is removed, the tree splits into separate components
• Each component's size is the number of nodes it contains
• The score is the product of all component sizes
• You need to count how many nodes achieve the maximum score

The solution uses DFS to traverse the tree and calculate each node's score by:

• Computing the size of each child subtree
• Computing the size of the "parent subtree" (if the node isn't the root)
• Multiplying all these sizes together to get the score
• Tracking the maximum score and counting how many nodes achieve it

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: The problem involves a tree structure where nodes are connected by parent-child relationships. A tree is a special type of graph (specifically, a connected acyclic graph).

Is it a tree?

• Yes: The problem explicitly states we have a binary tree rooted at node 0, with parent-child relationships defined by the parents array.

DFS

• Yes: Since we confirmed it's a tree problem, the flowchart leads us directly to DFS (Depth-First Search).

Conclusion: The flowchart suggests using a DFS approach for this problem.

This makes perfect sense because:

1. We need to traverse the entire tree to calculate scores for each node
2. For each node, we need to know the sizes of subtrees formed when that node is removed
3. DFS naturally computes subtree sizes during its traversal - when we visit a node, we can recursively calculate the size of its subtrees
4. The score calculation requires knowing both the sizes of child subtrees (computed during DFS traversal) and the size of the "parent component" (which is n - current_subtree_size)

The DFS approach allows us to efficiently compute all node scores in a single tree traversal, making it the ideal algorithm for this problem.

Intuition

When we remove a node from a tree, we're essentially "cutting" the tree at that point. This creates multiple disconnected components - the key insight is understanding what these components are:

1. Child subtrees: Each child of the removed node becomes the root of its own separate subtree
2. Parent component: Everything "above" the removed node (including siblings and their descendants) forms another component

To calculate a node's score, we need the sizes of all these components and multiply them together. The challenge is: how do we efficiently find these sizes for every node?

Here's where DFS becomes powerful. When we traverse a tree using DFS, we naturally visit all nodes in a subtree before returning to the parent. This means that as we return from a recursive call, we can carry back information about the subtree size.

Think of it like this: if we start DFS from the root and recursively explore each child, when the recursion "bubbles up" from a child, it can tell us "hey, my subtree has X nodes." This is exactly the information we need!

For any node i:

• When we visit its children through DFS, each child returns the size of its subtree
• These are the sizes of components that would be created if we removed node i
• The remaining nodes (those not in any child subtree of i) form the "parent component" with size n - total_nodes_in_subtree_of_i

The beauty of this approach is that we can calculate every node's score in a single tree traversal. As we visit each node:

1. Recursively get the sizes of all child subtrees
2. Calculate the parent component size as n - current_subtree_size
3. Multiply all these sizes together to get the score
4. Track the maximum score and count how many nodes achieve it

This way, we solve the entire problem with just one DFS traversal, making it both elegant and efficient.

Learn more about Tree, Depth-First Search and Binary Tree patterns.

Solution Approach

The implementation follows the DFS strategy we identified, with careful tracking of subtree sizes and score calculations.

Building the Tree Structure: First, we construct an adjacency list representation of the tree from the parents array:

g = [[] for _ in range(n)]
for i in range(1, n):
    g[parents[i]].append(i)

This creates a graph where g[i] contains all direct children of node i. Note that we only store parent-to-child edges since we'll traverse from root downward.

DFS Function Design: The core logic lies in the dfs(i, fa) function where:

• i is the current node being processed
• fa is the parent of node i (used to avoid revisiting the parent)
• Returns the size of the subtree rooted at node i

Calculating Subtree Sizes and Scores: For each node i, we initialize:

• cnt = 1: counts nodes in the current subtree (starting with the node itself)
• score = 1: accumulates the product of component sizes

As we traverse each child j of node i:

for j in g[i]:
    if j != fa:  # Skip the parent to avoid cycles
        t = dfs(j, i)  # Get child subtree size
        score *= t     # Multiply into the score
        cnt += t       # Add to current subtree size

Handling the Parent Component: After processing all children, if there are nodes outside the current subtree (i.e., n - cnt > 0), these form the parent component:

if n - cnt:
    score *= n - cnt

This accounts for all nodes "above" the current node in the tree.

Tracking Maximum Score: We use two global variables:

• mx: stores the highest score found so far
• ans: counts how many nodes achieve this highest score

if mx < score:
    mx = score
    ans = 1
elif mx == score:
    ans += 1

Complete Traversal: The algorithm starts with dfs(0, -1) from the root (node 0 with no parent), ensuring every node is visited exactly once. Each node's score is calculated using the sizes returned by its children's recursive calls plus the parent component size.

The time complexity is O(n) since we visit each node once, and the space complexity is O(n) for the recursion stack and adjacency list storage.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Consider a tree with 5 nodes where parents = [-1, 0, 0, 1, 1]:

Tree structure:
       0 (root)
      / \
     1   2
    / \
   3   4

Step 1: Build adjacency list

g[0] = [1, 2]  // node 0 has children 1 and 2
g[1] = [3, 4]  // node 1 has children 3 and 4
g[2] = []      // node 2 is a leaf
g[3] = []      // node 3 is a leaf
g[4] = []      // node 4 is a leaf

Step 2: DFS traversal starting from root

Let's trace through the DFS calls and see how scores are calculated:

Processing Node 3 (leaf):

• No children to process
• Subtree size = 1
• Parent component size = 5 - 1 = 4
• Score = 4
• Returns size 1 to parent

Processing Node 4 (leaf):

• No children to process
• Subtree size = 1
• Parent component size = 5 - 1 = 4
• Score = 4
• Returns size 1 to parent

Processing Node 1:

• Child 3 returns size 1 → score = 1
• Child 4 returns size 1 → score = 1 × 1 = 1
• Subtree size = 1 + 1 + 1 = 3
• Parent component size = 5 - 3 = 2
• Score = 1 × 1 × 2 = 2
• Returns size 3 to parent

Processing Node 2 (leaf):

• No children to process
• Subtree size = 1
• Parent component size = 5 - 1 = 4
• Score = 4
• Returns size 1 to parent

Processing Node 0 (root):

• Child 1 returns size 3 → score = 3
• Child 2 returns size 1 → score = 3 × 1 = 3
• Subtree size = 1 + 3 + 1 = 5
• Parent component size = 5 - 5 = 0 (no parent component for root)
• Score = 3 × 1 = 3

Step 3: Track maximum scores

Final scores for each node:

• Node 0: score = 3
• Node 1: score = 2
• Node 2: score = 4
• Node 3: score = 4
• Node 4: score = 4

Maximum score = 4, achieved by nodes 2, 3, and 4. Answer: 3 nodes have the highest score.

Verification of scores:

• Removing node 2: Creates one component of size 4 → score = 4 ✓
• Removing node 3: Creates one component of size 4 → score = 4 ✓
• Removing node 4: Creates one component of size 4 → score = 4 ✓
• Removing node 1: Creates components of sizes 1, 1, and 2 → score = 1×1×2 = 2 ✓
• Removing node 0: Creates components of sizes 3 and 1 → score = 3×1 = 3 ✓

This walkthrough demonstrates how the DFS approach efficiently calculates each node's score by using subtree sizes returned from recursive calls and computing parent component sizes as n - subtree_size.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm performs a depth-first search (DFS) traversal of the tree. Each node is visited exactly once during the DFS traversal. At each node, the algorithm:

• Iterates through all children of the current node (each edge is traversed once)
• Performs constant time operations (multiplication, comparison, addition)

Since we visit each of the n nodes exactly once and process each edge exactly once (there are n-1 edges in a tree), the total time complexity is O(n).

Space Complexity: O(n)

The space complexity consists of:

• The adjacency list g which stores all edges: O(n) space (storing n-1 edges across n lists)
• The recursive call stack for DFS: O(h) where h is the height of the tree. In the worst case (skewed tree), h = n, giving O(n) space
• A few variables (ans, mx, cnt, score, etc.): O(1) space

The dominant factor is the adjacency list and the potential recursive stack depth, resulting in an overall space complexity of O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Integer Overflow with Large Trees

The most critical pitfall in this problem is integer overflow when calculating the product of component sizes. For a tree with up to 10^5 nodes, the product can exceed standard integer limits.

Example scenario: Consider a star-shaped tree where the root has many children, each being a leaf. When removing the root, if there are 10^5 - 1 leaf nodes, the score would be 1^(10^5-1), which technically equals 1, but intermediate calculations with larger subtree sizes could overflow.

Solution: Python handles arbitrary precision integers automatically, but in languages like Java or C++, use long long or BigInteger types:

# Python handles this automatically
node_score *= child_subtree_size  # No overflow issues

# In Java, you'd need:
# long nodeScore = 1L;
# nodeScore *= childSubtreeSize;

2. Forgetting to Handle Leaf Nodes Correctly

A common mistake is not properly handling leaf nodes, which have no children. When a leaf node is removed, the only remaining component is the rest of the tree (size n-1), so the score should be n-1.

Incorrect approach:

# Wrong: Forgetting that leaf nodes still have a parent component
if not adjacency_list[node]:  # Leaf node
    node_score = 0  # WRONG!

Correct approach:

# The existing code handles this correctly:
if parent_component_size > 0:  # This covers leaf nodes
    node_score *= parent_component_size  # Score = n-1 for leaves

3. Incorrectly Building the Adjacency List

Some might accidentally create bidirectional edges or miss the parent-child relationship:

Incorrect:

# Wrong: Creating bidirectional edges
for i in range(1, n):
    adjacency_list[parents[i]].append(i)
    adjacency_list[i].append(parents[i])  # WRONG - creates cycles!

Correct:

# Only store parent-to-child edges
for child in range(1, n):
    parent = parents[child]
    adjacency_list[parent].append(child)

4. Not Initializing Score to 1

A subtle but critical error is initializing the node_score to 0 instead of 1:

Incorrect:

node_score = 0  # WRONG - multiplying by anything gives 0
for child in adjacency_list[node]:
    node_score *= child_subtree_size  # Always 0!

Correct:

node_score = 1  # Correct - identity element for multiplication

5. Forgetting Edge Case of Single Node Tree

When n=1 (single node tree), removing the only node leaves no components. The score should be 1 (empty product convention), not 0.

The solution handles this correctly: When n=1, no children exist, and parent_component_size = 1-1 = 0, so the if condition if parent_component_size > 0 is false, leaving node_score = 1.