Corjuc Eunice: Pagină nouă: = Cerința = Se dă un arbore cu `n` noduri, în care fiecare muchie are asociat un număr natural. Se cere răspunsul la `Q` întrebări de forma: dacă `u` şi `v` sunt două noduri din arbore, care este valoarea `xor` a tuturor numerelor asociate muchiilor situate pe lanţul ce uneşte `u` şi `v`? = Date de intrare = Fișierul de intrare `arbori_xorIN.txt` conține pe prima linie nume...

2024-01-03T20:29:56Z

Pagină nouă: = Cerința = Se dă un arbore cu <code>n</code> noduri, în care fiecare muchie are asociat un număr natural. Se cere răspunsul la <code>Q</code> întrebări de forma: dacă <code>u</code> şi <code>v</code> sunt două noduri din arbore, care este valoarea <code>xor</code> a tuturor numerelor asociate muchiilor situate pe lanţul ce uneşte <code>u</code> şi <code>v</code>? = Date de intrare = Fișierul de intrare <code>arbori_xorIN.txt</code> conține pe prima linie nume...

New page

= Cerința =
Se dă un arbore cu <code>n</code> noduri, în care fiecare muchie are asociat un număr natural. Se cere răspunsul la <code>Q</code> întrebări de forma: dacă <code>u</code> şi <code>v</code> sunt două noduri din arbore, care este valoarea <code>xor</code> a tuturor numerelor asociate muchiilor situate pe lanţul ce uneşte <code>u</code> şi <code>v</code>?

= Date de intrare =
Fișierul de intrare <code>arbori_xorIN.txt</code> conține pe prima linie numerele <code>n</code> şi <code>Q</code>, pe următoarele <code>n-1</code> linii câte o pereche de numere naturale ce reprezintă extremităţile unei muchii din arbore urmată de un număr natural ce reprezintă valoarea muchiei, iar pe următoarele <code>Q</code> linii câte o pereche de numere naturale ce reprezintă nodurile pentru care se cere <code>xor</code>-ul valorilor de pe lanţul ce le uneşte .

= Date de ieșire =
Fișierul de ieșire <code>arbori_xorOUT.txt</code> va conține pe primele <code>Q</code> linii răspunsurile la cele <code>Q</code> cerinţe.

= Restricții și precizări =

* <code>2 ≤ n ≤ 10.000</code>
* <code>1 ≤ Q ≤ 500.000</code>
* valorile asociate muchiilor sunt numere naturale cel mult egale cu <code>10.000</code>

== Exemplul 1 ==
arbori_xorIN.txt:

5 2

1 2 7

1 3 4

3 4 1

4 5 13

1 5

3 2

arbori_xorOUT.txt:

8

3

Explicație: Pentru prima cerinţă avem <code>4 ^ 1 ^ 13 = 8</code>, iar pentru a doua <code>4 ^ 7 = 3</code>.

== Exemplul 2 ==
arbori_xorIN.txt:

99999999 2

1 2 7

1 3 4

3 4 1

4 5 13

1 5

3 2

Output:

Input conditions not satisfied.

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
from collections import deque

def bfs(nod):
global coada, s, t
coada.append(nod)
while coada:
nod = coada.popleft()
for i in range(len(L[nod])):
vecin, cost = L[nod][i]
if t[nod] == vecin:
continue
coada.append(vecin)
t[vecin] = nod
s[vecin] = s[nod] ^ cost

def query(a, b):
return s[a] ^ s[b]

def verify_conditions(n, q):
if 2 <= n <= 10000 and 1 <= q <= 500000:
return True
else:
return False

fin = open("arbori_xorIN.txt", "r")
fout = open("arbori_xorOUT.txt", "w")

coada = deque()
L = [[] for _ in range(10009)]
s = [0] * 10009
t = [0] * 10009

n, q = map(int, fin.readline().split())

if not verify_conditions(n, q):
print("Input conditions not satisfied.")
fin.close()
fout.close()
exit()

for _ in range(n-1):
x, y, z = map(int, fin.readline().split())
L[x].append((y, z))
L[y].append((x, z))

bfs(1)

for _ in range(q):
a, b = map(int, fin.readline().split())
fout.write(str(query(a, b)) + '\n')

fin.close()
fout.close()

</syntaxhighlight>

3127 – Arbori xor - Revision history