3715. Sum of Perfect Square Ancestors Hard
1/**
2 * [3715] Sum of Perfect Square Ancestors
3 *
4 * 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.
5 * You are also given an integer array nums, where nums[i] is the positive integer assigned to node i.
6 * Define a value ti as the number of ancestors of node i such that the product nums[i] * nums[ancestor] is a <span data-keyword="perfect-square">perfect square</span>.
7 * Return the sum of all ti values for all nodes i in range [1, n - 1].
8 * Note:
9 *
10 * In a rooted tree, the ancestors of node i are all nodes on the path from node i to the root node 0, excluding i itself.
11 *
12 *
13 * <strong class="example">Example 1:
14 * <div class="example-block">
15 * Input: <span class="example-io">n = 3, edges = [[0,1],[1,2]], nums = [2,8,2]</span>
16 * Output: <span class="example-io">3</span>
17 * Explanation:
18 * <table style="border: 1px solid black;">
19 * <thead>
20 * <tr>
21 * <th style="border: 1px solid black;">i</th>
22 * <th style="border: 1px solid black;">Ancestors</th>
23 * <th style="border: 1px solid black;">nums[i] * nums[ancestor]</th>
24 * <th style="border: 1px solid black;">Square Check</th>
25 * <th style="border: 1px solid black;">ti</th>
26 * </tr>
27 * </thead>
28 * <tbody>
29 * <tr>
30 * <td style="border: 1px solid black;">1</td>
31 * <td style="border: 1px solid black;">[0]</td>
32 * <td style="border: 1px solid black;">nums[1] * nums[0] = 8 * 2 = 16</td>
33 * <td style="border: 1px solid black;">16 is a perfect square</td>
34 * <td style="border: 1px solid black;">1</td>
35 * </tr>
36 * <tr>
37 * <td style="border: 1px solid black;">2</td>
38 * <td style="border: 1px solid black;">[1, 0]</td>
39 * <td style="border: 1px solid black;">nums[2] * nums[1] = 2 * 8 = 16<br />
40 * nums[2] * nums[0] = 2 * 2 = 4</td>
41 * <td style="border: 1px solid black;">Both 4 and 16 are perfect squares</td>
42 * <td style="border: 1px solid black;">2</td>
43 * </tr>
44 * </tbody>
45 * </table>
46 * Thus, the total number of valid ancestor pairs across all non-root nodes is 1 + 2 = 3.
47 * </div>
48 * <strong class="example">Example 2:
49 * <div class="example-block">
50 * Input: <span class="example-io">n = 3, edges = [[0,1],[0,2]], nums = [1,2,4]</span>
51 * Output: <span class="example-io">1</span>
52 * Explanation:
53 * <table style="border: 1px solid black;">
54 * <thead>
55 * <tr>
56 * <th style="border: 1px solid black;">i</th>
57 * <th style="border: 1px solid black;">Ancestors</th>
58 * <th style="border: 1px solid black;">nums[i] * nums[ancestor]</th>
59 * <th style="border: 1px solid black;">Square Check</th>
60 * <th style="border: 1px solid black;">ti</th>
61 * </tr>
62 * </thead>
63 * <tbody>
64 * <tr>
65 * <td style="border: 1px solid black;">1</td>
66 * <td style="border: 1px solid black;">[0]</td>
67 * <td style="border: 1px solid black;">nums[1] * nums[0] = 2 * 1 = 2</td>
68 * <td style="border: 1px solid black;">2 is not a perfect square</td>
69 * <td style="border: 1px solid black;">0</td>
70 * </tr>
71 * <tr>
72 * <td style="border: 1px solid black;">2</td>
73 * <td style="border: 1px solid black;">[0]</td>
74 * <td style="border: 1px solid black;">nums[2] * nums[0] = 4 * 1 = 4</td>
75 * <td style="border: 1px solid black;">4 is a perfect square</td>
76 * <td style="border: 1px solid black;">1</td>
77 * </tr>
78 * </tbody>
79 * </table>
80 * <p data-end="996" data-start="929">Thus, the total number of valid ancestor pairs across all non-root nodes is 1.
81 * </div>
82 * <strong class="example">Example 3:
83 * <div class="example-block">
84 * Input: <span class="example-io">n = 4, edges = [[0,1],[0,2],[1,3]], nums = [1,2,9,4]</span>
85 * Output: <span class="example-io">2</span>
86 * Explanation:
87 * <table style="border: 1px solid black;">
88 * <thead>
89 * <tr>
90 * <th style="border: 1px solid black;">i</th>
91 * <th style="border: 1px solid black;">Ancestors</th>
92 * <th style="border: 1px solid black;">nums[i] * nums[ancestor]</th>
93 * <th style="border: 1px solid black;">Square Check</th>
94 * <th style="border: 1px solid black;">ti</th>
95 * </tr>
96 * </thead>
97 * <tbody>
98 * <tr>
99 * <td style="border: 1px solid black;">1</td>
100 * <td style="border: 1px solid black;">[0]</td>
101 * <td style="border: 1px solid black;">nums[1] * nums[0] = 2 * 1 = 2</td>
102 * <td style="border: 1px solid black;">2 is not a perfect square</td>
103 * <td style="border: 1px solid black;">0</td>
104 * </tr>
105 * <tr>
106 * <td style="border: 1px solid black;">2</td>
107 * <td style="border: 1px solid black;">[0]</td>
108 * <td style="border: 1px solid black;">nums[2] * nums[0] = 9 * 1 = 9</td>
109 * <td style="border: 1px solid black;">9 is a perfect square</td>
110 * <td style="border: 1px solid black;">1</td>
111 * </tr>
112 * <tr>
113 * <td style="border: 1px solid black;">3</td>
114 * <td style="border: 1px solid black;">[1, 0]</td>
115 * <td style="border: 1px solid black;">nums[3] * nums[1] = 4 * 2 = 8<br />
116 * nums[3] * nums[0] = 4 * 1 = 4</td>
117 * <td style="border: 1px solid black;">Only 4 is a perfect square</td>
118 * <td style="border: 1px solid black;">1</td>
119 * </tr>
120 * </tbody>
121 * </table>
122 * Thus, the total number of valid ancestor pairs across all non-root nodes is 0 + 1 + 1 = 2.
123 * </div>
124 *
125 * Constraints:
126 *
127 * 1 <= n <= 10^5
128 * edges.length == n - 1
129 * edges[i] = [ui, vi]
130 * 0 <= ui, vi <= n - 1
131 * nums.length == n
132 * 1 <= nums[i] <= 10^5
133 * The input is generated such that edges represents a valid tree.
134 *
135 */
136pub struct Solution {}
137
138// problem: https://leetcode.com/problems/sum-of-perfect-square-ancestors/
139// discuss: https://leetcode.com/problems/sum-of-perfect-square-ancestors/discuss/?currentPage=1&orderBy=most_votes&query=
140
141// submission codes start here
142
143impl Solution {
144 pub fn sum_of_ancestors(n: i32, edges: Vec<Vec<i32>>, nums: Vec<i32>) -> i64 {
145
146 }
147}
148
149// submission codes end
150
151#[cfg(test)]
152mod tests {
153 use super::*;
154
155 #[test]
156 fn test_3715() {
157 }
158}
159Back
© 2026 bowen.ge All Rights Reserved.