| Fişierul intrare/ieşire: | egal.in, egal.out | Sursă | Algoritmiada 2011, Runda 3 |
| Autor | Andrei Parvu, Bogdan-Cristian Tataroiu | Adăugată de |  Bogdan-Cristian Tataroiu •bogdan2412 |
| Timp execuţie pe test | 0.3 sec | Limită de memorie | 36864 kbytes |
| Scorul tău | N/A | Dificultate | N/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.in | egal.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 |
