← 返回题目列表

Codeforces · 375/D

D. 树和查询

中文机器翻译题面 查看原题

你有一棵由 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 之间的最短路径的长度(以边为单位)。