Sum of Perfect Square Ancestors

Challenge Points: 30

Level: Hard

You are given an integer n and an undirected tree rooted at node 0 with nodes 0..n-1. The tree is provided as edges of length n - 1, where edges[i] = [u, v] denotes an undirected edge. You are also given a positive-integer array nums where nums[i] is assigned to node i.

For each node i, let t_i be the number of its ancestors (on the path to root 0, excluding i) such that the product nums[i] * nums[ancestor] is a perfect square.
Return the sum of t_i over all i in [1, n-1].

Key insight: For any integers x, y, the product x * y is a perfect square iff their squarefree “signatures” are equal (i.e., the product of primes with odd exponent in their factorizations matches). So for each node, count how many ancestors share the same squarefree signature.

Example 1:

Input: n = 5 edges = [[0,1],[0,2],[1,3],[1,4]] nums = [6,10,15,6,10]

Output: 2

Explanation:

Squarefree signatures: 6 -> 2*3, 10 -> 2*5, 15 -> 3*5 Node 1 (10): ancestor [0 (6)] → different → t1 = 0 Node 2 (15): ancestor [0 (6)] → different → t2 = 0 Node 3 (6): ancestors [1 (10), 0 (6)] → matches node 0 → +1 Node 4 (10): ancestors [1 (10), 0 (6)] → matches node 1 → +1 Total = 0 + 0 + 1 + 1 = 2