Fişierul intrare/ieşire:minmaxtree.in, minmaxtree.outSursăBOI 2018
AutorTamio-Vesa NakajimaAdăugată detamionvTamio Vesa Nakajima tamionv
Timp execuţie pe test1 secLimită de memorie256000 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Minmaxtree

Tanaka a rezolvat de curând o problema clasică: dat fiind un arbore cu N vârfuri şi valori pe muchii, el a găsit valoarea maximă sau minimă pe K lanţuri din arbore. În mod interesant, toate aceste rezultate au fost distincte! Din nefericire, valorile iniţiale au fost pierdute.
Dându-se rezultatele lui Tanaka, cât şi structura arborelui original, poţi găsi o atribuire plauzibilă a valorilor pentru toate muchiile? Dacă poţi, Groot se va îndrăgosti de arborele creat şi vei primi 100 de puncte.

Date de intrare

Prima linie a fişierului de intrare minmaxtree.in va conţine numărul N.
Următoarele N - 1 linii vor conţine perechi de numere x y, cu 1 ≤ x, y ≤ N, ce semnifică că arborele are o muchie de la nodul x la nodul y. Nodurile arborelui sunt indexate de la 1 la N.
Următoarea linie a inputului va conţine numărul K.
Următoarele K linii vor conţine o descriere a rezultatelor lui Tanaka, un rezultat pe fiecare linie. Un rezultat care semnifică că maximul de pe drumul de la x la y a fost z va fi reprezentat de M x y z, şi unul care semnifică că minimul de pe drumul de la x la y a fost z va fi reprezentat de m x y z.
Se garantează că muchiile date formează un arbore, şi că toate valorile z sunt distincte.

Date de ieşire

Fişierul de ieşire minmaxtree.out va conţine N - 1 linii. Fiecare linie va conţine trei numere x y v care semnifică că în atribuirea ta de valori exită o muchie de la x la y cu greutatea v. Aceste muchii ar trebui să coincidă cu muchiile din fişierul de intrare, ignorând ordinea muchiilor. Mai mult, ordinea lui x şi y în cadrul unei muchii nu contează. Această atribuire ar trebui să ducă la rezultatele descrise.
Se garantează că există o atribuire de valori ce duce la rezultatele descrise.

Restricţii

  • 1 ≤ N ≤ 70.000
  • 1 ≤ K ≤ 70.000
  • 1 ≤ z ≤ 1.000.000.000
  • Pentru 7 puncte, N ≤ 1.000 şi z ≤ 1.000.
  • Pentru alte 22 puncte, Tanaka a găsit doar maxime.
  • Pentru alte 29 puncte, oricare două lanţuri pentru care Tanaka a găsit maxime nu se intersectează. De asemenea, oricare două lanţuri pentru care Tanaka a găsit minime nu se intersectează.

Exemple

minmaxtree.inminmaxtree.out
4
1 2
2 3
3 4
3
M 1 2 1
m 1 4 0
M 2 3 100
3 2 100
1 2 1
4 3 0


Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?