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 · Photo
click to show
885 · click to show
def getMaximumSum(matrix, k):
global idx
import heapq
from collections import deque
n = len(matrix)
rows = [deque(row) for row in matrix]
heap = []
for i in range(n):
if rows[i]:
heapq.heappush(heap, (-rows[i][0], i, True))
heapq.heappush(heap, (-rows[i][-1], i, False))
ans= 0
for _ in range(k):
while heap:
val, idx, is_left = heapq.heappop(heap)
if rows[idx]:
if is_left and rows[idx][0] == -val:
ans += rows[idx].popleft()
break
elif not is_left and rows[idx][-1] == -val:
ans += rows[idx].pop()
break
if rows[idx]:
heapq.heappush(heap, (-rows[idx][0], idx, True))
heapq.heappush(heap, (-rows[idx][-1], idx, False))
return ans
getMaximumSum✅✅
CISCO✅
985 ·