Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | petarbore.in, petarbore.out | Sursă | Baraj Shumen Juniori ICHB-Vianu - 2022 |
| Autor | Patrascanu Casian, Peticaru Alexandru | Adăugată de |  Comisie Juniori Vianu - ICHB •comisie_baraj_shumen_ichb_vianu_juniori |
| Timp execuţie pe test | 1 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Petarbore
Se da un arbore cu N noduri, fiecare muchie avand un cost. Pentru o submultime X de noduri ale arborelui definim urmatoarea functie:
f(X) = costul minim al unei muchii a carei capete fac parte din multimea X
Sa se calculeze suma valorilor lui f(X), pentru toate submultimile X, modulo 998244353.
Date de intrare
Fişierul de intrare petarbore.in va contine pe prima linie N, reprezentand numarul de noduri ale arobrelui.
Pe urmatoarele N-1 linii se vor afla muchiile arborelui, sub forma x y z reprezentand muchia si costul sau, in aceasta ordine.
Date de ieşire
În fişierul de ieşire petarbore.out va contine un singur numar, reprezentand suma modulo 998244353.
Restricţii
- Pentru 25 puncte, 1 ≤ N ≤ 15.
- Pentru 25 puncte, 1 ≤ N ≤ 200.
- Pentru 25 puncte, 1 ≤ N ≤ 5000 si muchiile vor avea costul 1 sau 2.
- Pentru 25 puncte, 1 ≤ N ≤ 5000.
Exemplu
| petarbore.in | petarbore.out |
|---|---|
| 4 1 2 1 1 3 1 3 4 2 | 10 |
Explicaţie
f({1, 2}) = 1, f({1, 3}) = 1, f({1, 2, 3}) = 1, f({3, 4}) = 2, f({1, 2, 4}) = 1, f({1, 3, 4}) = 1, f({2, 3, 4}) = 2, f({1, 2, 3, 4}) = 1
Restul submultimilor X, in afara de cele enumerate mai sus, au f(X) = 0
Suma valorilor lui f(X) va fi:
1 + 1 + 1 + 2 + 1 + 1 + 2 + 1 = 10
