主题

主题

 
   

D. Tree and Queries

原题:http://codeforces.com/problemset/problem/375/D

You have a rooted tree consisting of n vertices. Each vertex of the tree has some color. We will assume that the tree vertices are numbered by integers from 1 to n. Then we represent the color of vertex v as cv. The tree root is a vertex with number 1.

In this problem you need to answer to m queries. Each query is described by two integers vj, kj. The answer to query vj, kj is the number of such colors of vertices x, that the subtree of vertex vj contains at least kj vertices of color x.

You can find the definition of a rooted tree by the following link: http://en.wikipedia.org/wiki/Tree_(graph_theory).

Input

The first line contains two integers n and m (2 ≤ n ≤ 105; 1 ≤ m ≤ 105). The next line contains a sequence of integers c1, c2, ..., cn (1 ≤ ci ≤ 105). The next n - 1 lines contain the edges of the tree. The i-th line contains the numbers ai, bi (1 ≤ ai, bi ≤ n; ai ≠ bi) — the vertices connected by an edge of the tree.

Next m lines contain the queries. The j-th line contains two integers vj, kj (1 ≤ vj ≤ n; 1 ≤ kj ≤ 105).

Output

Print m integers — the answers to the queries in the order the queries appear in the input.

Examples

input

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

output

2

2

1

0

1

input

4 1

1 2 3 4

1 2

2 3

3 4

1 1

output

4


题目大意:

给出一棵大小为n的树,每个节点有一个颜色。

给出m个询问(u,k),每次询问一个节点u为根的子树中,颜色次数超过k的有多少个。


个人解法:


  • 子树问题转DFS序

既然只有子树查询,我们把DFS序做出来。问题转换为查询一段区间上出现次数大于k的数字有多少个。


然后我们可以使用莫队。

虽然有一个k的变量,但是莫队维护桶还是可以上的。

我们用一个Sum[i],表示出现次数为i的数字有多少个。每一次查询就是查询一个后缀和。

这个数组可以通过树状数组维护。

时间复杂度O(nsqrt(n)logn)。

codeforces评测机速度完全不虚。


对于维护后缀,事实上可以有一个地方改进。

我们萌生一种直接令Sum[i]为后缀和的想法。简单来说,我们令Sum[i]表示出现次数大于i的有多少个。

我们用Bucket[w]表示w的出现次数。当Bucket[w]--的时候,我们发现只有Sum[Bucket[w]]--,其余的均不变。当Bucket[w]++的时候类似。

于是事实上我们可以O(1)维护这个数组。同样适用于莫队。

时间复杂度O(nsqrt(n))。

代码如下:

http://codeforces.com/contest/375/submission/25952389


  • 树上合并

子树问题同样可以使用一些黑科技来合并。


比方说,Splay的启发式合并。

每个元素按照出现的次数排序。每一次合并相当于插入/修改。在插入完一个之后,这棵Splay的有序性会被打破。

于是我们暴力调整这棵Splay。

一个简单又粗暴的方法就是把这个节点删除,再重新加入。

不过也是比较靠谱的。

时间复杂度O(nlog^2n)。


(似乎这个方法不好推广到线段树合并上?)


在网上看到一种分治的方法,可以把时间复杂度将为O(nlogn),然而感觉复杂度证明比较奥妙重重。


人懒。毕竟本蒟比较追求“可以AC”+“代码好写”的方法……大概要成为夕阳红选手,写不动数据结构了……

 
 
评论