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

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()