La chiave per derivare quella formula è vedere come i vari percorsi si sovrappongono e ricordare che qualsiasi numero XOR stesso è uguale a 0. In particolare, Q (x, y) XOR Q (x, y) eguale a 0.
Derivazione rapida
F (u) è il percorso dal nodo radice a u. F (v) è il percorso dal nodo radice a v. Poiché qualsiasi numero XOR stesso è uguale a 0, F (u) XOR F (v) "annulla" tutti i nodi sopra il più basso antenato comune di uev, LCA (u, v). Quindi F (u) XOR F (v) = Q (LCA (u, v), u) XOR Q (LCA (u, v), v). Questa è la somma XOR di tutti i nodi sul percorso univoco da u a v, ad eccezione di LCA (u, v) stesso, poiché è attualmente conteggiata due volte. Quindi, se contiamo semplicemente una terza volta, otteniamo la somma di tutti i nodi in Q (u, v). Quindi Q (u, v) = F (u) XOR F (v) XOR LCA (u, v).
Sospetto che questa "prova" tralascia troppi dettagli per te o contenga alcuni passaggi di cui non sei già convinto, quindi ecco una versione molto più lunga:
The Thorough Derivation
Supponiamo che il nostro grafico sia un albero valido, e c'è un unico percorso univoco tra uev. Ciò garantisce che tu abbia un unico "antenato comune più basso", LCA (u, v), che io farà riferimento come a. Chiamerò il nodo radice r. Tieni presente che a potrebbe essere lo stesso nodo di u, v, a o anche tutti e tre. L'argomento che sto per mostrare dovrebbe funzionare anche in quei casi degenerati.
Quindi ci sono percorsi univoci (possibilmente di lunghezza zero) tra questi quattro nodi, come questo:
Seguendo l'editoriale, lascia che Q(x, y) denoti la somma XOR dei nodi sul percorso univoco da x a y .
Siamo interessati a Q(u, v) . Chiaramente, il percorso univoco da u a v passa attraverso a . Tuttavia, sarebbe errato dire che Q(u, v) = Q(u, a) XOR Q(a, v) perché ciò conterebbe il valore di a due volte. Fortunatamente, poiché XOR un valore di per sé risulta pari a zero, il conteggio di a tre volte equivale a contarlo una sola volta. Quindi l'affermazione corretta è:
Q(u, v) = Q(u, a) XOR Q(a, v) XOR A[a]
Successivamente, F(i) è definito come Q(r, i) . Quindi possiamo seguire la stessa logica di sopra e dire:
F(u) = Q(r, u) = Q(r, a) XOR Q(a, u) XOR A[a]
F(v) = Q(r, v) = Q(r, a) XOR Q(a, v) XOR A[a]
Ora, cos'è F(u) XOR F(v) ? Poiché l'operazione XOR è commutativa e associativa, possiamo riorganizzare in modo sicuro una serie di XOR come se fosse una serie di + s, che ci consente di fare questo:
F(u) XOR F(v) = (Q(r, a) XOR Q(a, u) XOR A[a]) XOR (Q(r, a) XOR Q(a, v) XOR A[a])
= (Q(r, a) XOR Q(r, a)) XOR (Q(a, u) XOR Q(a, v)) XOR (A[a] XOR A[a])
= 0 XOR (Q(a, u) XOR Q(a, v)) XOR 0
= Q(a, u) XOR Q(a, v)
Più intuitivo: ogni volta che XOR le somme di XOR di due percorsi sovrapposti, le parti che si sovrappongono semplicemente scompaiono, e restiamo solo con le somme XOR delle parti non sovrapposte dei percorsi.
Infine, ricorda che Q(u, v) = Q(u, a) XOR Q(a, v) XOR A[a] . Ora sappiamo che Q(a, u) XOR Q(a, v) equivale a F(u) XOR F(v) , che significa:
Q(u, v) = Q(u, a) XOR Q(a, v) XOR A[a]
= F(u) XOR F(v) XOR A[a]
E poiché ho definito a come LCA(u, v) , abbiamo finito.