Fişierul intrare/ieşire:regat.in, regat.outSursăLot Vrancea 2010, Baraj 1
AutorAdrian AirineiAdăugată deMishu91Andrei Misarca Mishu91
Timp execuţie pe test0.75 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Regat

Regele Gefghev se confruntă cu o nouă problemă de interes naţional. Regatul condus de el conţine N oraşe, numerotate de la 1 la N, legate între ele prin N–1 poteci bidirecţionale. Fiecare potecă are o anumită lungime exprimată în metri. Între oricare două oraşe există cel mult o singură potecă şi se poate ajunge din orice oraş în oricare alt oraş, mergând numai pe potecile existente. Regelui îi place să călătorească, de aceea el îşi ia concediu M zile şi plănuieşte să organizeze M călătorii. La începutul fiecărei zile Gefghev alege un oraş de pornire x şi vrea să parcurgă începând cu acel oraş un drum de lungime maximă. Drumul parcurs de rege este de fapt o succesiune de oraşe distincte ( a1 , a2 , a3 ... ak-1 , ak ) astfel încât există o potecă între oricare două oraşe ai şi ai+1 (i < k) iar a1 = x. Lungimea drumului este dată de suma lungimilor potecilor care-l compun. Fiindcă nu vrea să se plictisească, regele Gefghev vrea să parcurgă în fiecare zi un drum diferit. Două drumuri d1 = ( a1 , a2 , a3 ... ak-1 , ak ) şi d2 = ( b1 , b2 , b3 ... bp-1 , bp ) sunt diferite dacă:

  • k ≠ p sau
  • k = p şi există măcar o poziţie q astfel încât aq ≠ bq

Scrieţi un program care determină pentru regele Gefghev lungimea drumului parcurs în fiecare din cele M călătorii.

Date de intrare

Pe prima linie a fişierului de intrare regat.in se află două numere întregi N şi M separate printr-un singur spaţiu, cu semnificaţia din enunţ. Pe următoarele N-1 linii se află câte trei numere a, b şi c separate prin câte un singur spaţiu, având semnificaţia că există un drum de la oraşul a la oraşul b, iar acest drum are lungimea de c metri. Pe următoarele M linii se află câte un număr cuprins între 1 şi N, pe linia N+1+i aflându-se oraşul din care regele îşi începe a i-a călătorie.

Date de ieşire

În fişierul de ieşire regat.out se vor afla M numere naturale, pe linia i se va afla lungimea drumului parcurs de rege in călătoria din ziua i.

Restricţii

  • 1 ≤ N, M ≤ 100.000
  • Lungimile drumurilor sunt numere naturale cuprinse în intervalul [1, 10.000]
  • Regele poate începe mai multe călătorii din acelaşi oraş
  • Regele va avea întotdeauna posibilitatea de a efectua toate călătoriile
  • Pentru 20% din teste N ≤ 700
  • Pentru 40% din teste fiecare călătorie începe dintr-un oraş diferit

Exemplu

regat.inregat.out
8 5
1 2 3
2 3 5
3 4 14
2 6 3
2 7 9
7 8 10
5 6 20
1
2
1
4
3
26
23
22
42
28

Explicaţie

Prima călătorie începe în oraşul 1 şi se finalizează în orasul 5. Lungimea drumului este 26. Nu există alt oraş la o distanţă strict mai mare decât 26. A doua oară cand regele începe o calatorie din orasul 1, o poate încheia în oricare din oraşele 4 sau 8, lungimea drumului fiind 22.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content