Revizia anterioară Revizia următoare
Solutii Happy Coding 2
Problemele date in cadrul acestui concurs au fost folosite pentru a selecta cele 3 echipe care au reprezentat Universitatea Politehnica Bucuresti la etapa regionala sud-est europeana a concursului ACM ICPC, in anul 2005.
Expresii algebrice
Calatorie interplanetara
Razboiul lumilor
Solutia optima are complexitate O(N) si se realizeaza parcurgand arborele de 2 ori. La prima parcurgere fixam radacina arborelui in nodul 1. Vom calcula pentru fiecare nod i cate 2 valori: lungimea maxima a unui drum de la orasul i la orice alt oras din subarborele acestuia, {L1[i]}, si a lungimea maxima a unui drum de la orasul $i la un oras din subarborele acestuia, dar care este diferit de primul drum, {L2[i]} (practic, a doua lungime maxima a unui drum, care poate fi, eventual, egala cu lungimea primului). In a doua parcurgere vom calcula distanta maxima de la fiecare oras $i la orice alt oras si vom alege orasele pentru carea aceasta distanta maxima este minima. Pentru radacina arborelui am calculat deja aceasta valoare din prima parcurgere. Pentru orice alt nod i, distanta maxima de la i la orice alt oras este ori {L1[i]}, ori un drum ce trece prin parintele lui $i. Cel mai lung drum ce trece prin parintele lui i are lungimea egala cu distanta de la i la parintele lui i plus {L1[parinte[i]]}, in cazul in care drumul corespunzator lui {$L1[parinte[i]]} nu trece prin orasul $i, respectiv plus {L2[parinte[i]]}, in cazul in care drumul corespunzator lui {$L1[parinte[i]]} trece prin orasul $i.
