Sum of Perfect Square Ancestors
You are given an integer n and an undirected tree rooted at node 0 with n nodes numbered from 0 to n - 1. This is represented by a 2D array edges of length n - 1, where edges[i] = [ui, vi] indicates an undirected edge between nodes ui and vi.
You are also given an integer array nums, where nums[i] is the positive integer assigned to node i.
Define a value ti as the number of ancestors of node i such that the product nums[i] * nums[ancestor] is a perfect square.
Return the sum of all ti values for all nodes i in range [1, n - 1].
Note:
- In a rooted tree, the ancestors of node
iare all nodes on the path from nodeito the root node0, excludingiitself.
Example 1
Input
n = 3, edges = [[0,1],[1,2]], nums = [2,8,2]Output
3Node 1 has one valid ancestor pair and node 2 has two valid ancestor pairs, so the total is 3.
Example 2
Input
n = 3, edges = [[0,1],[0,2]], nums = [1,2,4]Output
1Only node 2 forms a perfect square product with its ancestor node 0, so the total is 1.
Constraints
- 1 <= n <= 10^5
- edges.length == n - 1
- edges[i] = [ui, vi]
- 0 <= ui, vi <= n - 1
- nums.length == n
- 1 <= nums[i] <= 10^5
- The input is generated such that edges represents a valid tree.
Asked at 3 companies
Practice questions like this out loud in a mock coding interview with a live AI interviewer. First one free.