palatulvoltaic

Palatulvoltaic

Tanaka a decis sa viziteze locul de unde vine toata electricitatea din univers, mai exact, $Palatul Voltaic$. $Palatul voltaic$ il putem modela ca pe un arbore cu $N$ noduri, unde nodurile reprezinta turnuri ale palatului, si muchiile reprezinta coridoare ale palatului. In fiecare camera se joaca cate un sport, pasii meciurilor acelui sport furnizand electricitatea $Palatului Voltaic$. Se stie ca, pentru sportul din camera $i$, intr-un meci faci exact $v{~i~}$ pasi. Odata aflat intr-o camera, poti juca *oricate* meciuri ale sportului din camera aceea.
Tanaka are, totodata, un pedometru (adica un dispozitiv care masoara cati pasi faci), care poate numara pana la $K$ pasi. Mai exact, in momentul in care Tanaka face cel de-al $K+1$-lea pas, el se reseteaza si o ia de la $0$ (precum kilometrajul la masina).

In vizita sa Tanaka isi incepe drumul dintr-un nod $x$, ales de el. Apoi, organizatorii palatului ii vor da un numar $d$ ales uniform aleator intre $1$ si $N$. Apoi, Tanaka viziteaza toate nodurile la distanta cel mult $d$ fata de $x$, jucand sau nu meciuri in camerele acelea. El va alege meciurile la care participa astfel incat la finalul vizitei sale, numarul de pasi pe care il arata pedometrul sau este maximizat. Tanaka ar vrea sa stie, pentru fiecare valoare posibila a lui $x$ de la $1$ la $N$, care este valoarea medie a numarului maxim de pasi pe care il poate arata pedometrul sau, tinand cont ca $d$ este ales aleator uniform intre $0$ si $N - 1$. Puteti calcula aceste valori?

In vizita sa Tanaka isi incepe drumul dintr-un nod $x$, ales de el. Apoi, organizatorii palatului ii vor da un numar $d$ ales uniform aleator intre $0$ si $N - 1$. Apoi, Tanaka viziteaza toate nodurile la distanta cel mult $d$ fata de $x$, jucand sau nu meciuri in camerele acelea. El va alege meciurile la care participa astfel incat la finalul vizitei sale, numarul de pasi pe care il arata pedometrul sau este maximizat. Tanaka ar vrea sa stie, pentru fiecare valoare posibila a lui $x$ de la $1$ la $N$, care este valoarea medie a numarului maxim de pasi pe care il poate arata pedometrul sau, tinand cont ca $d$ este ales aleator uniform intre $0$ si $N - 1$. Puteti calcula aceste valori?

h2. Date de intrare

* Pentru $10$ puncte, $N ≤ 20$ -- feedback testele 1, 3.
* Pentru alte $30$ de puncte, $N ≤ 1.000$ -- feedback testele 6, 13, 18.
* Pentru alte $10$ puncte, $K$ este ales uniform aleator intre $1$ si $1.000.000.000$, si valorile lui $v$ sunt alese uniform aleator independent intre $1$ si $K$ -- feedback testele 21, 24.

* Restul testelor de feedback fac parte din testele cele mai mari

h2. Exemplu