| 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 (u, v), where 
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, the number of nodes. The second line will contain N numbers, the i-th number, representing the 
. Each of the next N - 1 lines will contain a pair of nodes (u, v), each representing an edge of the tree.
Date de ieşire
The output will contain the sum of costs over all pairs of nodes (u, v), such that
Restricţii
- 1 ≤ N ≤ 100000
- 1 ≤ ≤ 30000
- For the first subtask (1 ≤ N ≤ 1000)
- For the second subtask,
for i = 1, 2,...n
Exemplu
| sumtree.in | sumtree.out |
|---|---|
| 5 2 7 14 22 77 1 2 1 3 2 4 4 5 | 442 |
Trebuie sa te autentifici pentru a trimite solutii. Click aici
