Lista de probleme 51

Se dă vectorul de tați al unui arbore cu rădăcină cu n noduri în care fiecare nod are asociată o valoare numerică. Determinați drumul de la rădăcină la un nod terminal pentru care suma valorilor asociate nodurilor este maximă.

Într-o firmă sunt n angajați, numerotați de la 1 la n, organizați ierarhic, astfel că fiecare angajat are un șef direct, cu excepția directorului general, care nu are șef. Fiecare angajat al firmei are un salariu cunoscut, exprimat printr-un număr natural. În firmă funcționează un sistem de recompensare a angajaților astfel încât câștigul fiecărui salariat este egal cu salariul său la care se adaugă media aritmetică a câștigurilor subordonaților săi direcți. Excepție fac angajații care nu au subordonați direcți, pentru care câștigul este egal cu salariul.

Determinați care este câștigul directorului general al firmei.

Se dau n numere naturale, $a_1,a_2,\dots ,a_n$, reprezentând valorile asociate nodurilor unui arbore. Construiţi arborele astfel încât suma valorilor L(u,v) să fie maximă, unde pentru orice două frunze u şi v, cu $u<v$, ale arborelui, L(u,v) reprezintă suma valorilor $a_i$ asociate nodurilor ce formează lanţul de la u la v.

Eșuînd în a-și regăsi adevărata identitate, Brush se refugiază în magicul tărâm al arborilor. Arbotra o sună și îi dă următoarea problemă: se dă un arbore cu N noduri, o rădăcină fixată, și M întrebări de forma: câte perechi neordonate de noduri pot forma, luând noduri doar din subarborele nodului X (inclusiv pe X).

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?

Se dă un arbore cu $N$ noduri și $N-1$ muchii etichetate cu o literă fiecare. Vom defini un drum $(x,y)$ ca fiind secvența de muchii care duc de la nodul $x$ la nodul $y$. De asemenea, vom considera drumurile $(x,y)$ si $(y,x)$ ca fiind același drum. Un drum poate fi palindromic dacă există o cale de a permuta toate literele parcurse in drumul respectiv în așa fel încât să formăm un drum palindromic.

Să se afle câte drumuri pot fi palindromice.

Se dă un arbore cu $N$ noduri înrădăcinat în nodul $1$, unde fiecare nod are un pondere asociat întreg $V_i$. Să se proceseze $Q$ evenimente de următoarele $3$ tipuri:

• $1kv$ – ponderele nodului $k$ devine egal cu $v$
• $2ab$ – să se afișeze ponderele minim al unui nod de pe drumul simplu de la nodul $a$ la nodul $b$.
• $3k$ – să se afișeze ponderele minim al unui nod din subarborele înrădăcinat în nodul $k$.

Se consideră un graf cu N noduri numerotate de la 1 la N și M operații de trei tipuri:

• 1 x y – se adaugă în graf muchia (x, y). Dacă muchia există deja, operația nu se efectuează
• 2 x y – întrebare: nodurile x și y se află sau nu în aceeași componentă conexă?
• 3 – care este numărul maxim de noduri dintr-o componentă conexă?

Trebuie să răspundeți la toate întrebările de tip 2 și 3.

În judeţul lui Dorel sunt n localităţi legate între ele prin m drumuri. Dorel e interesat să afle în câte moduri se pot alege n-1 drumuri din cele m date, astfel încât folosind aceste drumuri să se poată ajunge de la orice localitate la oricare alta.

Se dă un arbore cu n noduri şi rădăcina r, nodurile fiind etichetate cu numerele de la 1 la n. Se cere să se afle pentru fiecare nod i, câte noduri din subarborele cu rădăcina i au eticheta mai mică decât i.