http://www.elijahqi.win/2018/03/01/codeforces-375d/
题意翻译
给出一棵 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
c_{v}
cv? . 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
v_{j},k_{j}
vj?,kj? . The answer to query
v_{j},k_{j}
vj?,kj? is the number of such colors of vertices
x
x , that the subtree of vertex
v_{j}
vj? contains at least
k_{j}
kj? 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<=105;
1<=m<=105)( 2 <= n <= 10 5 ;
1 <= m <= 10 5 ). The next line contains a sequence of integers
c_{1},c_{2},…,c_{n}
c1?,c2?,…,cn?
(1<=c_{i}<=10^{5})
(1<=ci?<=105) . The next
【codeforces 375d Tree and Queries】n-1
n?1 lines contain the edges of the tree. The
i
i -th line contains the numbers
a_{i},b_{i}
ai?,bi?(1<=ai,bi<=n;
ai≠bi)( 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
v_{j},k_{j}
vj?,kj?(1<=vj<=n;
1<=kj<=105)( 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： 复制
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
说明
A subtree of vertex
v
v in a rooted tree with root
r
r is a set of verticesu:dist(r,v)+dist(v,u)=dist(r,u)u : d i s t ( r , v ) + d i s t ( v , u ) = d i s t ( 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即可
#include
#include
#include
#define N 110000
using namespace std;
inline char gc(){
static char now[1<<16],*S,*T;
if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);
if (T==S) return EOF;
}
return *S++;
}
inline int read(){
int x=0,f=1;
char ch=gc();
while(ch<'0'||ch>'9') {if (ch=='-') f=-1;
ch=gc();
}
while(ch<='9'&&ch>='0') x=x*10+ch-'0',ch=gc();
return x*f;
}
struct node1{
int y,next;
}data[N<<1];
struct node{
int l,r,id,bl,k;
}qr[N];
bool visit[N];
int num,h[N],in[N],out[N],w[N],c[N],ans[N],Ans[N],f[N],nn,n,m;
inline bool cmp(const node &a,const node &b){
return a.bl==b.bl?a.rl) update(--cl);
while(cr>r) update(cr--);
while(cr 
