【CF375D】Trees and Queries——树上启发式合并
2024-10-18 18:31:57
(题面不是来自Luogu)
题目描述
有一个大小为n且以1为根的树,树上每个点都有对应的颜色ci。现给出m次询问v, k,问以v为根的子树中有多少种颜色至少出现了k次。
输入格式
第一行两个数n,m表示树的大小以及询问的次数。
第二行n个数表示树上每个结点的颜色。
接下来的n-1行,每行两个数a, b表示树上的边。
接下来m行,每行两个数v, k表示询问。
输出格式
m行,每行一个数表示第i次询问的答案。
样例输入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
数据范围
2≤n≤100000
1≤m≤100000
1≤ci≤100000
1≤a, b≤n, a≠b
1≤v≤n, 1≤k≤100000
对于其中30%的数据保证n,m≤100且ci≤n
对于其中60%的数据保证n≤5000
(7:20)今天为了打这个题的正解学了dsu on tree。需要学习的同学请看我的上一篇博客。
树上启发式合并主要解决的就是这类静态子树统计问题。
对于这题,我们维护两个数组cnt和upr,分别表示某种颜色出现的数量和出现次数大于某个次数的颜色的种类数。每次暴力累计子树信息时,出现一个颜色先++cnt[color[i]],然后++upr[cnt[color[i]]]。容易想到,这样可以保证不重不漏地统计到所有达到upr[i]的颜色,并且不会重复累加。剩下的套dsu on tree板子即可。
代码:
- #include <cstdio>
- #include <iostream>
- #include <cctype>
- #include <cstring>
- #include <vector>
- #define maxn 100010
- using namespace std;
- template <class T>
- void read(T &x) {
- x = 0;
- char ch = getchar();
- while (!isdigit(ch))
- ch = getchar();
- while (isdigit(ch)) {
- x = x * 10 + (ch ^ 48);
- ch = getchar();
- }
- }
- int n, m, color[maxn], upr[maxn], cnt[maxn], ans[maxn];
- struct Query {
- int k, id;
- };
- vector<Query> Q[maxn];
- int head[maxn], top;
- struct E {
- int to, nxt;
- } edge[maxn << 1];
- inline void insert(int u, int v) {
- edge[++top] = (E) {v, head[u]};
- head[u] = top;
- }
- int size[maxn], son[maxn];
- void dfs(int u, int pre) {
- size[u] = 1;
- for (int i = head[u]; i; i = edge[i].nxt) {
- int v = edge[i].to;
- if (v == pre) continue;
- dfs(v, u);
- size[u] += size[v];
- if (size[son[u]] < size[v])
- son[u] = v;
- }
- }
- int CurSon;
- void cal(int u, int pre, int val) {
- if (val == -1)
- --upr[cnt[color[u]]];
- cnt[color[u]] += val;
- if (val == 1)
- ++upr[cnt[color[u]]];
- for (int i = head[u]; i; i = edge[i].nxt) {
- int v = edge[i].to;
- if (v == CurSon || v == pre) continue;
- cal(v, u, val);
- }
- }
- void dsu(int u, int pre, bool op) {
- for (int i = head[u]; i; i = edge[i].nxt) {
- int v = edge[i].to;
- if (v == pre || v == son[u]) continue;
- dsu(v, u, 0);
- }
- if (son[u])
- dsu(son[u], u, 1), CurSon = son[u];
- cal(u, pre, 1); CurSon = 0;
- for (int i = 0; i < Q[u].size(); ++i)
- ans[Q[u][i].id] = upr[Q[u][i].k];
- if (!op)
- cal(u, pre, -1);
- }
- int main() {
- // freopen("count.in", "r", stdin);
- // freopen("count.out", "w", stdout);
- read(n), read(m);
- for (int i = 1; i <= n; ++i)
- read(color[i]);
- int u, v;
- for (int i = 1; i < n; ++i) {
- read(u), read(v);
- insert(u, v), insert(v, u);
- }
- int k;
- for (int i = 1; i <= m; ++i) {
- read(v), read(k);
- Q[v].push_back((Query) {k, i});
- }
- dfs(1, 0);
- dsu(1, 0, 1);
- for (int i = 1; i <= m; ++i)
- printf("%d\n", ans[i]);
- return 0;
- }
最新文章
- centos6字符
- 【小白的CFD之旅】07 CFD常识
- ListView
- php插件开发
- Excel导入数据(97--2003版本)的ExcelHelper
- sort()的多种用法
- 剪花布条 --HDOJ 2087
- 更快的使用你的键盘:AUTOHOTKEY
- asp.net中怎样调用存储过程和存储过程的写法(转载,留着自己看)
- doT.js——前端javascript模板引擎问题备忘录
- java利用poi来读取execl表格返回对象
- StackExchange.Redis超时的问题
- [Swift]LeetCode845. 数组中的最长山脉 | Longest Mountain in Array
- ArcGIS 网络分析[3] 发布NAServer到ArcGIS for Server(以Server 10.4为例)
- mac系统 pip3 install scrapy 失败 No local packages or working download links found for incremental>;=16.10.1
- Confluence 6 配置字符集编码
- android的logcat详细用法!
- 20155321 《Java程序设计》实验报告一:Java开发环境的熟悉(Windows+IDEA)
- Exchange Powershell:Get-Counter (List connections to OWA )
- java mybatisGenerator with velocity
热门文章
- U138097 小鱼吃大鱼 埃氏筛
- SQL Server 列存储索引 第四篇:实时运营数据分析
- 4G DTU是什么 4G DTU的功能和特点
- 云计算管理平台之OpenStack块存储服务cinder
- python开发基础(二)运算符以及数据类型之float(浮点类型)
- 1到n整数中1出现的次数
- leetcode1Minimum Depth of Binary Tree
- GraphX 在图数据库 Nebula Graph 的图计算实践
- 使用bootstrap fileinput多文件拖拽上传的记录
- Spider_基础总结2_Request+Beautifulsoup解析HTML