D. Дерево и запросы
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Задано корневое дерево, состоящее из n вершин. Каждая вершина дерева имеет определенный цвет. Будем считать, что вершины дерева пронумерованы целыми числами от 1 до n. Тогда цвет вершины v будем обозначать cv. Корнем дерева является вершина с номером 1.

В задаче вам требуется ответить на m запросов. Каждый запрос характеризуется двумя целыми числами vj, kj. Ответ на запрос vj, kj — это количество таких цветов вершин x, что в поддереве вершины vj содержится как минимум kj вершин цвета x.

Определение корневого дерева можно прочитать по ссылке: http://ru.wikipedia.org/wiki/Дерево_(теория_графов).

Входные данные

В первой строке записаны два целых числа n и m (2 ≤ n ≤ 105; 1 ≤ m ≤ 105). В следующей строке записана последовательность целых чисел c1, c2, ..., cn (1 ≤ ci ≤ 105). В следующих n - 1 строках записаны ребра дерева. В i-ой строке записаны числа ai, bi (1 ≤ ai, bi ≤ n; ai ≠ bi) — вершины, соединенные ребром дерева.

Далее в m строках записаны запросы. В j-той строке записаны два целых числа vj, kj (1 ≤ vj ≤ n; 1 ≤ kj ≤ 105).

Выходные данные

Выведите m целых чисел — ответы на запросы в порядке появления запросов во входных данных.

Примеры
Входные данные
8 5
1 2 2 3 3 2 3 3
1 2
1 5
2 3
2 4
5 6
5 7
5 8
1 2
1 3
1 4
2 3
5 3
Выходные данные
2
2
1
0
1
Входные данные
4 1
1 2 3 4
1 2
2 3
3 4
1 1
Выходные данные
4
Примечание

Поддерево вершины v в корневом дереве с корнем r — это множество вершин дерева {u : dist(r, v) + dist(v, u) = dist(r, u)}. Где dist(x, y) — это длина кратчайшего по количеству ребер пути между вершинами x и y.