题意翻译

给出一棵 n 个结点的树,每个结点有一个颜色 c i 。 询问 q 次,每次询问以 v 结点为根的子树中,出现次数 ≥k 的颜色有多少种。

感谢@elijahqi 提供的翻译

题目描述

You have a rooted tree consisting of

n 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 n

. Then we represent the color of vertex

v v

as

cv c_{v}

. The tree root is a vertex with number 1.

In this problem you need to answer to

m m

queries. Each query is described by two integers

vj,kj v_{j},k_{j}

. The answer to query

vj,kj v_{j},k_{j}

is the number of such colors of vertices

x x

, that the subtree of vertex

vj v_{j}

contains at least

kj k_{j}

vertices of color

x x

.

You can find the definition of a rooted tree by the following link: http://en.wikipedia.org/wiki/Tree\_(graph\_theory).

输入输出格式

输入格式:
The first line contains two integers

n n

and

m m

$ (2<=n<=10^{5}; 1<=m<=10^{5}) $ . The next line contains a sequence of integers

c1,c2,...,cn c_{1},c_{2},…,c_{n}

(1<=ci<=105) (1<=c_{i}<=10^{5})

. The next

n1 n-1

lines contain the edges of the tree. The

i i

-th line contains the numbers

ai,bi 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 m

lines contain the queries. The

j j

-th line contains two integers

vj,kj v_{j},k_{j}

$ (1<=v_{j}<=n; 1<=k_{j}<=10^{5}) $ .

输出格式:
Print

m m

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

输入输出样例

输入样例#1: 复制
输出样例#1: 复制
输入样例#2: 复制
输出样例#2: 复制

说明

A subtree of vertex

v v

in a rooted tree with root

r r

is a set of vertices $ {u :dist(r,v)+dist(v,u)=dist(r,u)} $ . Where

dist(x,y) dist(x,y)

is the length (in edges) of the shortest path between vertices

x x

and

y y

.

考虑子树一定是dfs序列上一个连续的区间 那么每次对子树操作总相当于针对dfs序上的一段连续区间操作

就可以莫队了 设ans表示出现次数超过i次的颜色数 f[i]表示i号颜色出现的次数 Ans相对应的记录每个询问的答案 那么考虑每个颜色出现一定是从0~xx 那么我每出现一次 我即对ans进行修改即可 并不需要区间修改 然后相应的减去的时候 也是这时候的出现次数-1  然后对应的ans数组再减1即可

 

分类: 莫队

elijahqi

退役了 现在在商院 偶尔打CF,有时有ACM regional也去玩一下

发表评论