Снег выпал на ферме, и Беси лепит из него снежную корову.
Причём Беси хочет, чтобы та выглядела как можно более натурально.
Но в этом году она лепит фигуру в виде дерева, состоящего из \(N\) снежков
\((1\le N\le 10^5)\) соединённых \(N-1\) ветками, каждая из которых соединяет
пару снежков так, что имеется уникальный путь между каждой парой снежков.
Беси добавила нос к одному из снежков, поэтому он представляет собой голову
этой абстрактной снежной коровы. Она обозначила это снежок числом 1.
Чтобы усилить визуальный эффект, она планирует покрасить некоторые из снежков
различными цветами. Цвета обозначаются числами в интервале \(1 \ldots 10^5\),
и у Беси неограниченное количество красок всех цветов.
Когда Беси красит снежок в определённый цвет, все снежки в его поддереве
также красятся в этот же цвет. (Снежок \(y\) находится в поддереве снежка \(x\),
если \(x\) находится на пути от \(y\) к головному снежку).
Занимаясь покраской, Беси обеспечивает, чтобы все цвета, которыми она красила
снежки, оставались видимыми. Например, если у снежка есть цвета \([1,2,3]\)
и Беси красит цветом \(4\), на снежке останутся следы цветов \([1,2,3,4]\).
После некоторого количества раскрашиваний, Беси хочет узнать, как раскрашена часть
её коровы. Полнота цветов("colorfulness") снежка \(x\) равно количеству различных
цветов \(c\), которыми раскрашен этот снежок \(x\). Если Беси спросит Вас о снежке
\(x\), Вы должны ответить сумму полноты цветов всех снежков в поддереве \(x\).
Помогите Беси определить полноту цветов в определённые моменты времени.
ОЦЕНИВАНИЕ:
\(Q\) определено ниже.
- Тесты 2-3 удовлетворяют \(N\le 10^2, Q\le 2\cdot 10^2.\)
- тесты 4-6 удовлетворяют \(N\le 10^3, Q\le 2\cdot 10^3.\)
ФОРМАТ ВВОДА (файл snowcow.in):
Первая строка содержит
\(N\), и количество запросов
\(Q\) (
\(1\le Q\le 10^5\)).
Каждая из последующих \(N-1\) строк содержит два разделённых одиночным пробелом
целых числа \(a\) и \(b\), описывающих ветки, соединяющие снежки \(a\) и \(b\) (\(1 \le a, b \le N\)).
Каждая из последних \(Q\) строк содержит запрос. Запрос имеет вид
1 x c
и означает. что Беси закрасила цветом \(c\) снежок \(x\) и всё его поддерево.
Строка вида
2 x
Это запрос на сумму "полноцветностей" всех снежков в поддереве \(x\).
\(1\le x\le N\) и \(1\le c\le 10^5.\)
ФОРМАТ ВЫВОДА (файл snowcow.out):
Для каждого запроса типа 2, выведите сумму "полноцветностей" соответствующего
поддерева.
Заметим. что Вы должны использовать 64-ное целое, чтобы избежать переполнения.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 18
1 2
1 3
3 4
3 5
1 4 1
2 1
2 2
2 3
2 4
2 5
1 5 1
2 1
2 2
2 3
2 4
2 5
1 1 1
2 1
2 2
2 3
2 4
2 5
|
1
0
1
1
0
2
0
2
1
1
5
1
3
1
1
|