3127 – Arbori xor

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 numerele n şi Q, pe următoarele n-1 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 Q linii câte o pereche de numere naturale ce reprezintă nodurile pentru care se cere xor-ul valorilor de pe lanţul ce le uneşte .

Date de ieșire

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

Restricții și precizări

• 2 ≤ n ≤ 10.000
• 1 ≤ Q ≤ 500.000
• valorile asociate muchiilor sunt numere naturale cel mult egale cu 10.000

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 4 ^ 1 ^ 13 = 8, iar pentru a doua 4 ^ 7 = 3.

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>