== include(page="template/taskheader" task_id="kdist") ==
p<>. Bujorel s-a apucat de pomicultură şi a însămânţat un arbore (graf conex aciclic) cu $N$ noduri, fiecare nod având o culoare dată dintr-un interval $[1, K]$. Acum, după ce arborele a crescut, el doreşte să ştie, pentru fiecare culoare, suma distanţelor dintre toate perechile de noduri ale arborelui ce au culoarea respectivă. Distanţa dintre două noduri se defineşte ca fiind numărul de muchii de pe drumul dintre cele două noduri.
Deoarece Bujorel a folosit foarte mult îngrăşământ la plantarea arborelui, acesta a crescut foarte mult şi voi trebuie să scrieţi un program care calculează suma distanţelor dintre nodurile cu aceeaşi culoare.
Poveste şi cerinţă...
h2. Date de intrare
p<>. Pe prima linie a fişierului kdist.in se află două numere naturale $N$ şi $K$, numărul de noduri ale arborelui, respectiv numărul de culori în care sunt vopsite nodurile. Pe următoarele $N-1$ linii este descris arborele, fiecare linie conţinând două numere naturale $x$ şi $y$, reprezentând o muchie dintre nodul $x$ şi nodul $y$. În continuare sunt prezente $N$ linii, a $i$-a dintre aceste linii având un număr întreg $c$ aparţinând intervalului $[1, K]$ reprezentând culoarea nodului $i$.
Fişierul de intrare $kdist.in$ ...
h2. Date de ieşire
p<>. Fişierul $kdist.out$ va conţine $K$ linii, cea de-a $i$-a linie conţinând suma distanţelor dintre toate perechile de noduri ce au culoarea $i$.
În fişierul de ieşire $kdist.out$ ...
h2. Restricţii
* $1 ≤ K ≤ N ≤ 200 000$
* În calcularea sumei distanţelor dintre nodurile cu aceeaşi culoare, fiecare pereche de noduri $(x, y)$ va fi considerată o singură dată.
* $... ≤ ... ≤ ...$
h2. Exemplu
table(example). |_. kdist.in |_. kdist.out |_. Explicaţie |
| 6 3
1 2
1 3
3 4
3 5
5 6
1
2
2
1
2
3
|2
6
0
| Pentru culoarea 1 avem o pereche: (1, 4), cu distanţa 2
Pentru culoarea 2 avem 3 perechi: (2, 3) cu distanţa 2, (2, 5) cu distanţa 3 si (3, 5) cu distanţa 1.
Pentru culoarea 3 avem un singur nod cu această culoare, deci răspunsul este 0.
|
table(example). |_. kdist.in |_. kdist.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicaţie
...
== include(page="template/taskfooter" task_id="kdist") ==
