CodeForces 375D Tree and Queries 莫队||DFS序
2024-10-06 11:33:33
题意:有一颗以1号节点为根的树,每一个节点有一个自己的颜色,求出节点v的子数上颜色出现次数>=k的颜色种类。
题解:使用莫队处理这个问题,将树转变成DFS序区间,然后就是开一个数据记录下出现次数为k次的颜色数目,查询的时候直接返回这个数组中的对应的值就行了。
注意的就是记得将节点的颜色传递给dfs序对应位置的颜色。 这个忘记了找了好久的bug。
代码:
#include<bits/stdc++.h>
using namespace std;
#define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout);
#define LL long long
#define ULL unsigned LL
#define fi first
#define se second
#define pb push_back
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
#define _S(X) cout << x << ' ';
#define __S(x) cout << x << endl;
typedef pair<int,int> pll;
const int INF = 0x3f3f3f3f;
const LL mod = (int)1e9+;
const int N = 2e5 + ;
int in[N], out[N], col[N], cc[N], cnt[N], num[N], ans[N];
vector<int> son[N];
int tot, n, m, blo;
struct Node{
int l, r, id, k;
}q[N];
bool cmp(Node x1, Node x2){
if(x1.l/blo != x2.l/blo) return x1.l/blo < x2.l/blo;
return x1.r < x2.r;
}
void Add(int c){
num[++cnt[c]]++;
}
void Remove(int c){
num[cnt[c]--]--;
}
void dfs(int o, int u){
in[u] = ++tot;
cc[tot] = col[u];
for(int i = ; i < son[u].size(); i++){
if(son[u][i] == o) continue;
dfs(u, son[u][i]);
}
out[u] = tot;
}
int main(){
scanf("%d%d", &n, &m);
for(int i = ; i <= n; i++)
scanf("%d", &col[i]);
blo = sqrt(n);
int u, v;
for(int i = ; i < n; i++){
scanf("%d%d", &u, &v);
son[u].pb(v);
son[v].pb(u);
}
dfs(-,);
for(int i = ; i <= m; i++){
q[i].id = i;
scanf("%d%d", &u, &v);
q[i].k = v;
q[i].l = in[u];
q[i].r = out[u];
}
sort(q+, q++m, cmp);
// cout << "vujgfuy" << endl;
int l = , r = ;
for(int i = ; i <= m; i++)
{
while(r < q[i].r) Add(cc[++r]);
while(r > q[i].r) Remove(cc[r--]);
while(l < q[i].l) Remove(cc[l++]);
while(l > q[i].l) Add(cc[--l]);
ans[q[i].id] = num[q[i].k];
}
for(int i = ; i <= m; i++)
printf("%d\n", ans[i]);
return ;
}
CF375 D
最新文章
- 取代 Windows Search
- WEB前端开发学习:源码canvas 雪
- 拓扑编号 vijos1790
- House Building---hdu5538(求表面积水题)
- WM (Constants)
- zImage转换为uImage
- 漂亮的表格样式(使用CSS样式表控制表格样式)
- UWP:使用Behavior实现FlipView简单缩放效果
- JAVA课程设计 刘舒婷 201521123096
- POI导出EXCEL,浏览器不兼容,文件名称乱码,文件无法打开解决方法
- AWS EC2 通过Linux终端:使用ssh连接到Linux实例
- 内存的一些magic number和debug crt(0xCCCCCCCC和0xCDCDCDCD,debug版本的CRT为了方便调试程序的初始值)
- AngularJS封装UEditor
- phaser相关
- 如何创建自己的python包
- 反向代理负载均衡-----nginx
- (转)MapReduce Design Patterns(chapter 7 (part 1))(十三)
- Verilog MIPS32 CPU(五)-- CP0
- Apache2.4和IIS7整合共享80端口测试
- CSS3 选择器 修改 整数个样式