Fişierul intrare/ieşire:egal.in, egal.outSursăAlgoritmiada 2011, Runda 3
AutorAndrei Parvu, Bogdan-Cristian TataroiuAdăugată debogdan2412Bogdan-Cristian Tataroiu bogdan2412
Timp execuţie pe test0.6 secLimită de memorie36864 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Egal

Toată lumea îl ştie pe TractoMarm, cel care numără noduri din arbori mai repede decât îşi numără alţii degetele de la mâini. Zilele trecute, TractoMarm s-a gândit să se ”joace” cu cele N seifuri ale lui Bercea, cel pentru care unitatea de măsură a valorii este milionul de euro. Cele N seifuri sunt dispuse sub forma unui arbore (graf conex aciclic), având ca rădăcină seiful cu numărul 1. Fiecare seif are asociată o cheie cu care seiful poate fi deschis. Din păcate (sau din fericire), pot exista două sau mai multe seifuri care să poată fi deschise cu aceeaşi cheie. Ştiind acest lucru TractoMarm doreşte să afle, pentru fiecare seif in parte x, care este cheia care deschide cele mai multe seifuri din subarborele lui x.

Date de intrare

Fişierul de intrare egal.in conţine pe prima linie N, numărul de seifuri ale lui Bercea.
Pe următoarele N - 1 linii se găsesc câte doua numere x şi y semnificând că există o legătură între seiful x şi seiful y.
Pe ultima linie se află N numere, al i-lea dintre acestea semnificând indicele cheii care deshide seiful i.

Date de ieşire

În fişierul de ieşire egal.out veţi afişa N linii. Linia cu numărul i va conţine indicele cheii care are cea mai mare frecvenţă în subarborele lui i şi de câte ori apare aceasta.

Restricţii

  • 1 ≤ N ≤ 100 000
  • În caz că există mai multe chei cu număr maxim de apariţii se va afişa cea cu indicele minim
  • Indicele unei chei se încadrează pe un întreg pe 32 de biţi cu semn
  • Atentie! TractoMarm vă aminteşte că memoria disponibilă pentru stivă este de maxim 8 MB!

Exemplu

egal.inegal.out
7
1 2
1 3
3 4
3 5
5 6
5 7
1 3 2 2 2 1 1
1 3
3 1
2 3
2 1
1 2
1 1
1 1
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content