CoderForces-375D

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 c_v. 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 v_j, k_j. The answer to query v_j, k_j is the number of such colors of verticesx, that the subtree of vertex v_j contains at least k_j 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 ≤ 10⁵; 1 ≤ m ≤ 10⁵). The next line contains a sequence of integers c₁, c₂, ..., c_n (1 ≤ c_i ≤ 10⁵). The next n - 1 lines contain the edges of the tree. The i-th line contains the numbers a_i, b_i (1 ≤ a_i, b_i ≤ n; a_i ≠ b_i) — the vertices connected by an edge of the tree.

Next m lines contain the queries. The j-th line contains two integers v_j, k_j (1 ≤ v_j ≤ n; 1 ≤ k_j ≤ 10⁵).

Output

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

Example

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

Input

Output

Note

A subtree of vertex v in a rooted tree with root r is a set of vertices{u : dist(r, v) + dist(v, u) = dist(r, u)}. Where dist(x, y) is the length (in edges) of the shortest path between vertices x and y.

题解：首先，通过dfs，可以把查询一棵树的子树转化为查询一段区间[l,r]。接下来，把整个区间分成n/sqrt(n)+1份，将查询按照l所在的区间排序，在同一区间内，将查询按r排序(由大到小)。对于查询，用一个数组表示某颜色数为x的颜色的个数，查询这个数组用分块法查询。

AC代码：

#include <iostream>  
#include<cstdio>  
#include<cstring>  
#include<string>  
#include<algorithm>   
#include<queue>  
#include<cmath>  
#include<vector>   
using namespace std;


typedef long long ll;
const int maxn = 100000 + 3000;
const int SIZE = 300;
int bnt[maxn], block[maxn / SIZE + 10], cnt[maxn];
int l[maxn], r[maxn], dfs_clock;
int c[maxn], cval[maxn], ans[maxn], n, m;
vector<int> g[maxn];


struct Query
{
int l, r, k, id;
Query() {}
Query(int lx, int rx, int kk, int i) 
{
l = lx;
r = rx;
k = kk;
id = i;
}
bool operator <(const Query &q) const
{
if (l / SIZE != q.l / SIZE) 
return l<q.l;
return r>q.r;
}
}querys[maxn];


void dfs(int u, int fa)
{
l[u] = ++dfs_clock;
cval[l[u]] = c[u];
int sz = g[u].size();
for (int i = 0; i<sz; ++i)
{
int v = g[u][i];
if (v == fa) 
continue;
dfs(v, u);
}
r[u] = dfs_clock;
}


void Insert(int k, int x)
{
bnt[k] += x;
block[k / SIZE] += x;
}
void Add(int v)
{
int p = ++cnt[cval[v]];
Insert(p, 1);
Insert(p - 1, -1);
}


void Dec(int v)
{
int p = --cnt[cval[v]];
Insert(p, 1);
Insert(p + 1, -1);
}


int cal(int k)
{
int sum = 0, p = k / SIZE;
for (int i = k; i<(p + 1)*SIZE; ++i)
sum += bnt[i];
for (int i = p + 1; i*SIZE<maxn; ++i)
sum += block[i];
return sum;
}


void solve()
{
memset(cnt, 0, sizeof(cnt));
memset(bnt, 0, sizeof(bnt));
memset(block, 0, sizeof(block));
Insert(0, n);
Add(1);
int l = 1, r = 1;
for (int i = 0; i<m; ++i)
{
while (querys[i].l<l) Add(--l);
while (querys[i].r>r) Add(++r);
while (querys[i].l>l) Dec(l++);
while (querys[i].r<r) Dec(r--);
ans[querys[i].id] = cal(querys[i].k);
}
}


int main()
{
cin >> n >> m;
for (int i = 0; i <= n; ++i) 
g[i].clear();
dfs_clock = 0;
for (int i = 1; i <= n; ++i)
cin >> c[i];
int u, v, k;
for (int i = 0; i<n - 1; ++i)
{
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}


dfs(1, -1);


for (int i = 0; i<m; ++i)
{
cin >> v >> k;
querys[i] = Query(l[v], r[v], k, i);
}
sort(querys, querys + m);
solve();
for (int i = 0; i < m; ++i)
cout << ans[i] << endl;
return 0;
}

View Code