Perfect Square Ancestor Pairs
Preview mode. Log in to edit, run, submit, and save progress.
Medium
Perfect Square Ancestor Pairs
You are given a rooted tree with n nodes numbered from 0 to n - 1, rooted at node 0. Each node i has a positive integer nums[i]. For every node except the root, count how many of its ancestors have a value that forms a perfect square when multiplied with nums[i]. Return the total count over all nodes.
Examples
Example 1
Input:
5 0 1 0 2 1 3 1 4 2 8 3 18 12
Output:
3
Explanation: Valid ancestor pairs are (1, 0), (3, 1), and (3, 0).
Approach hint
A product x * y is a perfect square when x and y have the same square-free part.
Common mistake
Skipping assumptions, edge cases, or trade-offs can make an otherwise good answer feel incomplete.
solution.cpp