Lista de probleme 4

Filtrare

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?

#3868 Planete

Tocmai s-a lansat un nou joc de computer. Ești un explorator spațial într-un univers cu N planete, fiecare are un teleportor către o altă planetă însemnând că de pe planeta curentă poți merge cătra planeta unde te poți teleporta. Legăturile sunt unidirecționate. Întrebarea este dacă tu acum ai fi pe planeta i, câte rute de teleportare trebuie să folosești astfel încât să ajungi pe o planetă pe care ai mai fost deja. Trebuie calculată pentru fiecare planetă această valoare.

Se consideră un graf neorientat conex cu n noduri și n muchii. Să se determine numărul arborilor parțiali ai grafului.

#3325 Ohoo

Porumbeii au pornit un război crâncen împotriva ciorilor, dar ele au construit garduri defensive pe toate rutele pe care le-ar putea folosi armata porumbeilor pentru a le ataca cetatea. Pentru a ajunge la cetatea ciorilor armata trebuie sa treacă de gardurile construite de ciori.