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, . You must calculate the sum cost of every pair nodes , where and u ≠ v. For a pair of nodes [Unparseable or potentially dangerous LaTeX formula! Error 2 : def] 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, 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?