Fişierul intrare/ieşire:	sumtree.in, sumtree.out	Sursă	IIOT 2022-23 Runda I
Autor	Vlad-Mihai Bogdan	Adăugată de	Buca Mihnea-Vicentiu •UnknownPercentage
Timp execuţie pe test	0.75 sec	Limită de memorie	262144 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Sumtree

You are given a tree with N nodes. Each node has values assigned to it, value[i]. You must calculate the sum cost of every pair nodes (u, v), where gcd(value[u], value[v]) > 1 and u ≠ v. For a pair of nodes (u, v), we define the cost of that path to be the sum of value of all nodes that lie inside the (u, v) path.

Date de intrare

The first line of the input will contain N (1 ≤ N ≤ 100000), the number of nodes. The second line will contain N numbers, the i-th number, representing the value[i] (1 ≤ value[i] ≤ 30000). Each of the next N - 1 lines will contain a pair of nodes (u, v), each representing an edge of the tree.

For tests worth 20 points (1 ≤ N ≤ 1000)
For tests worth 20 more points, value[i] = value1 for i = 1, 2,...n

Date de ieşire

The output will contain the sum of costs over all pairs of nodes (u, v), such that gcd(value[u], value[v]) > 1

Exemplu

Cum se trimit solutii?