Fişierul intrare/ieşire:spiridusi.in, spiridusi.outSursăONI 2015 Clasele 11-12
AutorVlad GavrilaAdăugată deassa98Andrei Stanciu assa98
Timp execuţie pe test0.2 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Spiridusi

Mei şi Satsuki s-au întors de curând în casa de vacanţă a familiei lor. Această casă este formată din N camere, unite între ele prin N-1 culoare, astfel încât să se poată ajunge din orice cameră în orice altă cameră. Intrarea în casă se face prin camera 1. Deoarece casa n-a fost locuită timp de mai multe luni, în fiecare cameră i s-au stabilit si spiriduşi de praf.
Cele două fete doresc să-şi amenajeze un spaţiu de joacă întins pe mai multe camere. Ele vor să stabilească două camere a şi b (nu neapărat distincte), astfel încât drumul cel mai scurt de la intrarea în casă până în camera b trece prin camera a. Fetele vor merge apoi din camera a în camera b pe drumul cel mai scurt (fără a trece de două ori prin aceeaşi cameră), gonind spiriduşii de praf aflaţi în fiecare cameră prin care trec, inclusiv pe cei din camerele a şi b. După ce fetele ajung în camera b, ele consideră că toate camerele din care au gonit spiriduşii de praf au fost alese pentru spaţiul de joacă.
Fetele au stabilit pentru fiecare cameră i un coeficient pi care reprezintă cât de plăcută ar fi camera i pentru spaţiul lor de joacă. În plus, ele au convenit că nu vor goni în total mai mult de C spiriduşi ai prafului din camerele prin care trec.

Cerinta

Cunoscând valorile lui N şi C, numărul de spiriduşi ai prafului si , coeficienţii pi pentru fiecare cameră i, cât şi modul în care sunt unite camerele prin culoare, să se determine suma maximă a coeficienţilor p ai camerelor alese pentru un spaţiu de joacă ce respectă condiţiile impuse de Mei şi Satsuki.

Date de intrare

Pe prima linie a fişierului de intrare spiridusi.in se vor afla două numere naturale N şi C cu semnificaţia din enunţ. Pe a doua linie se vor afla N numere naturale separate prin câte un spaţiu, al i-lea dintre acestea reprezentând numărul de spiriduşi si aflaţi în camera i. Pe a treia linie se vor afla N numere întregi separate prin câte un spaţiu, al i-lea dintre acestea reprezentând coeficientul pi al camerei i. Pe următoarele N-1 linii se vor afla câte două numere întregi x şi y separate printr-un spaţiu, semnificând existenţa unui culoar ce uneşte camerele x şi y.

Date de ieşire

În fişierul de ieşire spiridusi.out se va afişa o singură linie conţinând un singur număr natural, reprezentând suma maximă a coeficienţilor p ai camerelor alese pentru un spaţiu de joacă ce respectă condiţiile impuse de Mei şi Satsuki.

Restricţii

  • 1 ≤ N ≤ 100 000
  • 1 ≤ C ≤ 20 000 000
  • 1 ≤ si ≤ 20 000 000, pentru orice i, 1 ≤ i ≤ N.
  • -10000 ≤ pi ≤ 10000, pentru orice i, 1 ≤ i ≤ N.
  • Pentru 20% din teste, fiecare cameră are maximum 2 vecini.
  • Pentru 30% din teste, N ≤ 1 000.
  • Se garantează că pentru orice cameră x, numărul total de spiriduşi aflaţi în camerele de pe drumul cel mai scurt de la camera 1 la camera x nu depăşeşte 1 000 000 000.

Exemplu

spiridusi.inspiridusi.out
6 8
2 4 6 2 4 1
3 10 11 -2 4 5
1 2
2 3
2 4
4 5
4 6
13

Explicaţie

Dacă alegem camerele a = 2 şi b = 6, obţinem un spaţiu de joacă format din camerele 2, 4 şi 6.
Numărul total de spiriduşi goniţi din aceste camere este 4 + 2 + 1 = 7, care este mai mic sau egal decât C = 8.
Suma coeficienţilor p ai acestor camere este 10 + (-2) + 5 = 13, maximul posibil ce se poate obţine.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?