你有一棵由 n 个顶点组成的有根树。树的每个顶点都有某种颜色。我们假设树顶点用 1 到 n 的整数进行编号。然后我们将顶点v的颜色表示为cv。树根是编号为 1 的顶点。
在此问题中,您需要回答 m 个查询。每个查询由两个整数vj、kj 描述。查询vj的答案,kj是顶点x的这种颜色的数量,使得顶点vj的子树至少包含kj个颜色x的顶点。
您可以通过以下链接找到有根树的定义:http://en.wikipedia.org/wiki/Tree_(graph_theory)。
输入
第一行包含两个整数 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 个整数 — 按照查询在输入中出现的顺序查询的答案。
示例
输入 #1
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
输出 #1
2 2 1 0 1
输入 #2
4 1 1 2 3 4 1 2 2 3 3 4 1 1
输出 #2
4
注意
根为 r 的有根树中顶点 v 的子树是一组顶点 {u : dist(r, v) + dist(v, u) = dist(r, u)}。其中 dist(x, y) 是顶点 x 和 y 之间的最短路径的长度(以边为单位)。