Сніжна корова Бессі

На ферму випав сніг, і Бессі, як завжди на початку зими, будує снігову корову! Зазвичай вона намагається зробити свою скульптуру максимально схожою на справжню корову. Але цього року, відчувши натхнення, вона вирішила створити абстрактну скульптуру у формі дерева, що складається з $n$ сніжків, з'єднаних n - 1 гілкою. Кожна гілка з'єднує пару сніжків, і між будь-якими двома сніжками існує унікальний шлях.

Бессі додала ніс до одного з сніжків, щоб він представляв голову абстрактної снігової корови. Цей сніжок вона позначила номером $1$. Щоб додати більше візуального інтересу, вона планує художньо пофарбувати деякі сніжки в різні кольори, використовуючи старі молочні відра, наповнені кольоровим барвником, і розбризкуючи його на скульптуру. Кольори позначаються цілими числами від $1$ до 10^5, і у Бессі є необмежений запас відер з барвниками всіх можливих кольорів.

Коли Бессі бризкає на сніжок відром з фарбою, всі сніжки в його піддереві також заливаються цією ж фарбою (сніжок $y$ знаходиться в піддереві сніжка $x$, якщо $x$ лежить на шляху від $y$ до головного сніжка). Розбризкуючи кожен колір з великою обережністю, Бессі стежить за тим, щоб усі кольори, якими був розбризканий сніжок, залишалися видимими. Наприклад, якщо сніжок мав кольори [$1$, $2$, $3$], а Бессі залила його кольором $4$, то сніжок матиме кольори [$1$, $2$, $3$, $4$].

Після того, як Бессі кілька разів оббризкає сніжки, вона може захотіти дізнатися, наскільки барвиста частина її снігової корови. "Барвистість" сніжка $x$ дорівнює кількості таких різних кольорів $c$, якими він пофарбований. Якщо Бессі запитає вас про сніжок $x$, ви повинні відповісти, вказавши суму значень барвистості всіх сніжків у піддереві $x$.

Допоможіть Бессі визначити барвистість її снігової корови в певні моменти часу.