Deloitte | COGNIZANT | IBM | CAPGEMINI
import math
from collections import defaultdict, deque
def is_perfect_square(x):
root = int(math.isqrt(x))
return root * root == x
def solve(n, val, edge):
tree = defaultdict(list)
for u, v in edge:
tree[u].append(v)
tree[v].append(u)
parent = [-1] * n
path = [[] for _ in range(n)]
queue = deque([0])
visited = [False] * n
visited[0] = True
while queue:
node = queue.popleft()
for neighbor in tree[node]:
if not visited[neighbor]:
visited[neighbor] = True
parent[neighbor] = node
path[neighbor] = path[node] + [node]
queue.append(neighbor)
total_sum = 0
for i in range(1, n):
vi = 0
for anc in path[i]:
if is_perfect_square(val[i] * val[anc]):
vi += 1
total_sum += vi
return total_sum
n=int(input())
val=[int(i) for i in input().split()]
edge=[[int(i) for i in input().split()] for _ in range(n-1)]
print(solve(n,val,edge))
Tree Climber✅✅
929 ·