题目链接
题目大意 给定一棵树，n个节点，m个询问。
每次询问以 vi 为根的子树中，点数大于等于 ki 的颜色个数。
题解 对于这种询问子树的问题，经常会转到序列上。毕竟，序列较树有着无比优越性。
比如说，莫队算法。
利用dfs序将树转到序列上后，就可以套用莫队算法了。
维护区间时需要维护每种颜色的个数 cnti ，同时要维护颜色大于等于i的颜色个数 sumi 。
每次删除一个数，就把这种颜色的cnt减一，由于只有这种颜色变化了，所以sum变化的只有原来的 cntcoli ，所以在减一之前，先把 sumcntcoli 减一。
当加入一个数时，先把这个颜色的cnt加一，然后， sumcntcoli 也要加一。
#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int M=100005;
int col[M],L[M],R[M],dfs_clock,s;
int ans[M],cnt[M],sum[M],tmp[M];
vectoredge[M];
struct Query{
int L,R,num,id;
}q[M];
inline void rd(int&res){
res=0;
char c;
while(c=getchar(),!isdigit(c));
do res=res*10+(c^48);
while(c=getchar(),isdigit(c));
}
void rec(int x,int f){
L[x]=++dfs_clock;
for(int i=0;
iq[i].L){
L--;
cnt[col[L]]++;
sum[cnt[col[L]]]++;
}
while(Lq[i].R){
sum[cnt[col[R]]]--;
cnt[col[R]]--;
R--;
}
ans[q[i].id]=sum[q[i].num];
}
for(int i=0;
i 遗留问题 【codeforces|codeforces 375D Tree and Queries】这题还可以用map的启发式合并来写。
推荐阅读
- 技术|为参加2021年蓝桥杯Java软件开发大学B组细心整理常见基础知识、搜索和常用算法解析例题（持续更新...)
- codeforces B. Young Explorers
- codeforces C. Mere Array
- codeforces D. Omkar and Bed Wars
- codeforces C. Omkar and Waterslide
- codeforces B. Omkar and Infinity Clock
- codeforces B. Ternary Sequence
- 求桥，边双连通缩点
- 题库-CF|【Codeforces Round 370 (Div 2) E】【线段树 等比数列 区间合并】Memory and Casinos 赌场区间[l,r] l进r先出的概率
- 题库-CF|【Codeforces Round 263 (Div 2)C】【贪心 哈弗曼思维】Appleman and Toastman 每个非1size子树延展为2子树的最大权