Count how many nodes in a tree are “good” based on the values in their subtrees.
Problem
You are given a rooted tree with n nodes labeled from 0 to n - 1, where node 0 is the root. Each node has an integer value.
A node is called good if the values of all nodes in its subtree satisfy the condition required by the problem’s definition. In the common formulation, a node is good when its value is the same as every other node value in its subtree, or when it matches the subtree property that must be checked via a DFS over descendants.
Return the number of good nodes in the tree.
Intuition
This is a tree traversal problem where the answer is derived from information gathered from children to parent. A depth-first search is typically used to compute subtree information and decide whether each node is good.
Input Format
- The tree structure is provided implicitly or via parent-child relations.
- Each node has an associated integer value.
- The exact judge input is platform-specific and may include arrays describing edges or parent links.
You should focus on the tree property and subtree traversal rather than parsing details.
Output Format
Return a single integer: the number of nodes that satisfy the good-node condition.
Constraints
- The input describes a tree with
nnodes. 1 <= nis assumed.- Node values fit in standard integer ranges.
- A recursive or iterative tree traversal should run in linear or near-linear time.
Because the exact original statement is not provided here, treat these as prep-oriented constraints rather than official ones.
Example 1
Input
n = 5 edges = [[0,1],[0,2],[1,3],[1,4]] values = [5,5,5,5,5]
Output
5
Explanation
Every node has the same value as all nodes in its subtree, so all nodes are good.
Example 2
Input
n = 5 edges = [[0,1],[0,2],[1,3],[1,4]] values = [1,1,2,1,1]
Output
4
Explanation
Node 2 is not good because its subtree value differs from the root-subtree condition used in this illustrative version. The remaining nodes satisfy the subtree rule.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.