Editing 3127 – Arbori xor

= 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>