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 vertices x , 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.orgwikiTree_(graph_theory).
输入描述:
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).
输出描述:
Print m integers — the answers to the queries in the order the queries appear in the input.
示例1
输入
8 5<br />1 2 2 3 3 2 3 3<br />1 2<br />1 5<br />2 3<br />2 4<br />5 6<br />5 7<br />5 8<br />1 2<br />1 3<br />1 4<br />2 3<br />5 3<br />4 1<br />1 2 3 4<br />1 2<br />2 3<br />3 4<br />1 1<br />
输出
2<br />2<br />1<br />0<br />1<br />4<br />
备注:
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.
加载中...