codeforces 375d Tree and Queries

codeforces 375d Tree and Queries

​​ 题意翻译

给出一棵 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: ​​ 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 )

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

(1<=c_{i}<=10^{5}) (1<=ci​<=105) . The next

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 )

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 vertices u: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 )

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 110000using 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

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。