==Include(page="template/raw")==

Se considera un arbore (graf conex aciclic) cu $N$ varfuri, fara radacina fixata. Drept radacina, poate fi ales oricare dintre varfuri. Sa presupunem ca a fost ales varful cu numarul {$T$}. Intre oricare varf si $T$ exista un drum unic care contine fiecare varf al arborelui cel mult o singura data (un drum intre varfurile $i$ si $j$ este o secventa de varfuri, care incepe cu {$i$}, se termina cu {$j$}, iar intre oricare doua varfuri consecutive exista o muchie in arbore). Fiecarui varf {$i$}(inclusiv {$T$}) trebuie sa i se asocieze o valoare {$V~i~$}, mai mare sau egala cu {$0$}, astfel incat suma valorilor varfurilor de pe drumul dintre $i$ si radacina {$T$}, impartita la {$K$}, sa dea restul {$R~i~$}. Se defineste costul arborelui cu radacina fixata in {$T$}, {$C~T~$}, ca fiind suma valorilor asociate fiecarui nod. Dintre toate posibilitatile de alegere a valorilor $V~i~$ care respecta conditia precizata anterior, se va alege aceea pentru care $C~T~$ este minim.
Se constata usor ca alegand alt varf drept radacina, de exemplu, varful {$S$}(diferit de {$T$}), $C~S~$ nu este neaparat egal cu {$C~T~$}.

Se considera un arbore (graf conex aciclic) cu $N$ varfuri, fara radacina fixata. Drept radacina, poate fi ales oricare dintre varfuri. Sa presupunem ca a fost ales varful cu numarul {$T$}. Intre oricare varf si $T$ exista un drum unic care contine fiecare varf al arborelui cel mult o singura data (un drum intre varfurile $i$ si $j$ este o secventa de varfuri, care incepe cu {$i$}, se termina cu {$j$}, iar intre oricare doua varfuri consecutive exista o muchie in arbore). Fiecarui varf {$i$}(inclusiv {$T$}) trebuie sa i se asocieze o valoare {$V{~i~}$}, mai mare sau egala cu {$0$}, astfel incat suma valorilor varfurilor de pe drumul dintre $i$ si radacina {$T$}, impartita la {$K$}, sa dea restul {$R{~i~}$}. Se defineste costul arborelui cu radacina fixata in {$T$}, {$C{~T~}$}, ca fiind suma valorilor asociate fiecarui nod. Dintre toate posibilitatile de alegere a valorilor $V{~i~}$ care respecta conditia precizata anterior, se va alege aceea pentru care $C{~T~}$ este minim.
Se constata usor ca alegand alt varf drept radacina, de exemplu, varful {$S$}(diferit de {$T$}), $C~S~$ nu este neaparat egal cu {$C{~T~}$}.

h2. Cerinta