Задача python .

Question

Задача python .

Soul Leveling Ученик (70), на голосовании 23 часа назад

Дано дерево с N узлами (1 ≤ N ≤ 10^5). Каждый узел имеет назначенное ему значение. "Хороший путь" — это путь в дереве, на котором наибольший общий делитель (НОД) всех значений узлов на этом пути равен 1.

Требуется вычислить количество хороших путей в дереве.

Входные данные:
Первая строка содержит целое число N — количество узлов в дереве.
Вторая строка содержит N целых чисел a1, a2 , …, aN— значения в узлах.
Следующие N−1 строк содержат по два целых числа u и v — ребро между узлами u и v.

Выходные данные:
Выведите одно целое число — количество хороших путей в дереве.
Ограничения:
1 ≤ N ≤ 10^5
1 ≤ aj ≤ 10^5
входные данные

выходные данные

Answer 1

 from collections import defaultdict 
from math import gcd 
 
def count_good_paths(n, values, edges): 
    graph = defaultdict(list) 
    for u, v in edges: 
        graph[u].append(v) 
        graph[v].append(u) 
 
    def dfs(node, parent, current_gcd): 
        current_gcd = gcd(current_gcd, values[node - 1]) 
        if current_gcd == 1: 
            return 1 
        total_paths = 0 
        for neighbor in graph[node]: 
            if neighbor != parent: 
                total_paths += dfs(neighbor, node, current_gcd) 
        return total_paths 
 
    total_good_paths = 0 
    for i in range(1, n + 1): 
        total_good_paths += dfs(i, -1, 0) 
     
    return total_good_paths 
 
n = 5 
values = [2, 3, 4, 5, 6] 
edges = [(1, 2), (1, 3), (2, 4), (2, 5)] 
print(count_good_paths(n, values, edges))