Fişierul intrare/ieşire:arb2.in, arb2.outSursăONI 2010 - Baraj
AutorAdrian Airinei, Marius StroeAdăugată deMishu91Andrei Misarca Mishu91
Timp execuţie pe test0.15 secLimită de memorie36864 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Arb2

Se dă un arbore T cu n noduri, numerotate de la 1 la n, având rădăcina în nodul 1. Fiecare muchie (x, y), de la nodul x la nodul y, al arborelui are o lungime dată, d(x, y). Rădăcina transmite un mesaj tuturor celorlalte noduri din arbore. Timpul după care o frunză primeşte mesajul este egal cu suma lungimilor muchiilor de pe drumul de la rădăcină la această frunză.

Se doreşte ca durata transmisiei mesajului de la rădăcină la fiecare frunză să fie identică. Pentru aceasta avem la dispoziţie operaţia de incrementare, care poate fi aplicată asupra oricărei muchii (x, y) şi constă în creşterea lungimii muchiei cu o unitate. Costul aplicării operaţiei de incrementare asupra unei muchii (x, y) este c(x, y). Operaţia poate fi aplicată în mod repetat asupra aceleiaşi muchii.

Determinaţi costul total minim al operaţiilor necesare ca mesajul să ajungă în acelaşi timp în frunze.

Date de intrare

Pe prima linie a fişierului de intrare arb2.in se află numărul natural n. Următoarele n - 1 linii conţin câte patru numere naturale x y d(x, y) c(x, y), separate prin câte un singur spaţiu, având semnificaţia din enunţ.

Date de ieşire

În fişierul de ieşire arb2.out se va scrie pe prima linie costul minim cerut.

Restricţii

  • 1 ≤ n ≤ 100 000
  • 1 ≤ d ≤ 10 000
  • 1 ≤ c ≤ 10 000
  • Pentru 20% din teste n va fi egal cu 3.
  • Pentru alte 30% din teste costul operaţiei de incrementare pentru orice muchie va fi egal cu 1.

Exemplu

arb2.inarb2.outarb2.inarb2.out
7
1 2 2 1
2 4 2 1
2 5 1 1
1 3 1 1
3 6 2 1
3 7 1 1
3
9
1 2 3 1
2 4 4 1
2 5 2 1
1 3 2 10
3 6 4 1
3 7 1 10
7 8 1 2
7 9 1 1
12

Explicaţie

În primul exemplu se vor incrementa muchiile (2, 5), (1, 3) şi (3, 7) cu o unitate. Cum toate au costul 1, răspunsul va fi egal cu 3.

În cel de-al doilea exemplu se vor incrementa muchiile:

  • (2, 5) până la lungimea 4 cu costul 2
  • (3, 6) până la lungimea 5 cu costul 1
  • (7, 8) până la lungimea 4 cu costul 6
  • (7, 9) până la lungimea 4 cu costul 3

Costul minim cerut este 2+1+6+3=12.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content