Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | countfefete.in, countfefete.out | Sursă | ONI 2018, Baraj |
| Autor | Teodor Ionescu | Adăugată de |  Radu Muntean •heracle |
| Timp execuţie pe test | 1.5 sec | Limită de memorie | 131072 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Countfefete
Romeo Fefetastic locuieşte în cartierul băieţilor buni şi are N prieteni în cartier. Acest cartier este reprezentat ca un arbore cu N noduri, unde în fiecare nod stă câte un prieten. Fiecare dintre prietenii lui are câte o valoare, v[i], 1 ≤ i ≤ N.
Înainte ca Romeo să plece la plimbare cu motoreta prin cartier, el îşi face o listă cu toţi prietenii pe la care vrea să treacă pentru a-i vizita. Acesta va trece succesiv pe la toţi prietenii săi, de fiecare dată alegând drumul minim. Practic, Romeo se va plimba prin toate nodurile care aparţin subarborelui conex cu număr minim de noduri care include toţi prietenii din lista sa, subarbore notat cu S.
El cunoaşte cum arată cartierul şi ştie că în peregrinajul său va trece şi prin faţa caselor unor prieteni care nu apar pe listă, deci nu îi va vizita. După ce a trecut pe la toţi prietenii pe care şi-a propus să îi viziteze, el decide să se oprească la nodul celui mai nevaloros prieten dintre toate nodurile prin care a trecut, pentru a-l învăţa şi pe acesta cum se fac punctele. Prietenul cel mai nevaloros locuieşte în nodul cu cea mai mică valoare din subarborele S. În caz că acel prieten se află deja pe lista sa, îl va vizita de două ori.
Dacă Romeo îşi vizitează prietenii din nodurile n1 , n2 , ..., nk , şi se opreşte în mod excepţional la prietenul cel mai nevaloros care ar sta în nodul n nevaloros , atunci definim valoarea plimbării efectuate ca fiind v[n1] xor v[n2] xor ... xor v[nk] xor v[nnevaloros]. În caz că sunt mai mulţi prieteni la fel de nevaloroşi, Romeo merge la unul singur dintre
aceştia.
Lui Romeo Fefetastic îi place mai mult gânditul decât acţiunea. Aşadar, îşi imaginează că vrea să viziteze toate submulţimile posibile de prieteni şi se întreabă care ar fi suma pentru toate plimbările posibile.
Se cere aşadar găsirea sumei valorilor plimbărilor pentru toate submulţimile nevide de prieteni pe care Romeo le poate vizita şi afişarea acestei sume modulo 109 + 7.
Date de intrare
Pe primul rând al fişierului de intrare countfefete.in apare numărul de prieteni din cartier N.
Pe al doilea rând apare şirul v format din N numere, unde v[i] reprezintă valoarea prietenului care stă în nodul i.
Pe fiecare dintre următoarele N – 1 rânduri se va afla o pereche de numere x şi y, cu semnificaţia că de la nodul x la nodul y există un drum direct.
Date de ieşire
În fişierul de ieşire countfefete.out se va scrie suma cerută modulo 109 + 7.
Restricţii
- 1 ≤ N ≤ 200 000
- 0 ≤ v[x] ≤ 1 000 000 000, pentru orice 1 ≤ x ≤ N
- Pentru teste în valoare de 15 puncte se garantează că N ≤ 15
- Pentru alte teste în valoare de 25 de puncte se garantează că N ≤ 5 000
- Pentru alte teste în valoare de 15 puncte se garantează că N ≤ 20 000
- Pentru alte teste în valoare de 15 de puncte se garantează că N ≤ 70 000
Exemplu
| countfefete.in | countfefete.out |
|---|---|
| 3 7 3 2 1 2 2 3 | 21 |
| 3 1 1 1 1 3 2 3 | 3 |
| 5 1 3 7 2 5 1 2 2 3 2 4 4 5 | 98 |
Explicaţie
Pentru testul 1:
Avem 3 prieteni cu valorile v[1]=7, v[2]=3 şi v[3]=2
Prietenii din cartier formează un lanţ 1 – 2 – 3.
Considerăm toate submulţimile nevide de prieteni şi calculăm valoarea plimbărilor:
Pentru submulţimea {1} va trece prin {1}, deci valoarea plimbării = v[1] ^ v[1] = 0.
Pentru submulţimea {2} va trece prin {2}, deci valoarea plimbării = v[2] ^ v[2] = 0.
Pentru submulţimea {3} va trece prin {3}, deci valoarea plimbării = v[3] ^ v[3] = 0.
Pentru submulţimea {1, 2} va trece prin {1, 2}, iar valoarea minimă este în v[2] = 3, deci valoarea plimbării = v[1] xor v[2] xor v[2] = 7.
Pentru submulţimea {2, 3} va trece prin {2, 3}, iar valoarea minimă este în v[3] = 2, deci valoarea plimbării = v[2] xor v[3] xor v[3] = 3.
Pentru submulţimea {1, 3} va trece prin {1, 2, 3}, iar valoarea minimă este în v[3] = 2, deci valoarea plimbării = v[1] xor v[3] xor v[3] = 7.
Pentru submulţimea {1, 2, 3} va trece prin {1, 2, 3}, iar valoarea minimă este în v[3] = 2, deci valoarea plimbării = v[1] xor v[2] xor v[3] xor v[3] = 4.
Suma valorilor tuturor plimbărilor posibile va fi astfel
0 + 0 + 0 + 7 + 3 + 7 + 4 = 21.
