Counting the Subtrees That Agree
Each node of a tree holds a value. A node's SUBTREE is that node together with everything below it, the tree being rooted at node 1. Call a subtree UNIFORM when every node in it holds the same value.
Print how many of the n subtrees are uniform.
4 nodes, values 1 1 2 2, edges 1-2 1-3 3-4 -> 3
2 nodes, values 3 3 -> 2
## Every leaf counts
A leaf's subtree is a single node, and a single node trivially agrees with itself. So every leaf contributes 1, always, whatever value it holds.
That is the base case, and on many trees it is most of the answer. Any solution that returns fewer than the number of leaves has a bug in exactly that spot.
## The recurrence
A subtree at u is uniform when two things hold for every child c:
· c's own subtree is uniform
· c holds the same value as u
uniform[u] = AND over children c of ( uniform[c] and value[c] == value[u] )
with the empty AND at a leaf being true. Count the nodes where uniform holds.
Comparing u only against its CHILDREN is enough. If a child matches u and its own subtree
already agrees internally, then everything under that child equals the child, which equals
u. Agreement is transitive, so no deeper comparison is needed.
## Why not compare against the whole subtree
Collecting each subtree's set of values and checking it has size 1 is correct and quadratic in
the worst case, because a path of n nodes copies n, then n-1, then n-2 values upwards.
The single boolean carries the same information in constant space per node, which is the usual trade in this topic: keep the smallest fact the parent can actually use.
## Boundaries
A single node answers 1.
A tree where every value is identical answers n, and the tests include a star of eight equal
values to confirm that.
## Cost
Time O(n). Space O(n).