【CF1042F】Leaf Sets
2024-09-04 14:55:32
【CF1042F】Leaf Sets
题面
题解
对于一个根节点\(x\),考虑其子树内的所有\(lca\)为它的叶子节点到它的距离\(d_1<d2<...<d_m\)。
那么对于中间最小的\(d_i+d_{i+1}>K\),我们可以将\(i\)之前的所有叶子节点合并成一个大点,并以深度\(d_i\)向上合并,再将\(d_{i+1}...d_m\)向上合并即可。
这样子用数据结构维护复杂度是\(O(n\log n)\)的。
然而我们发现只有\(d_i\)继续向上合并才有用,那么只要保留这个\(d_i\)就行了,复杂度\(O(n)\)。
代码
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
inline int gi() {
register int data = 0, w = 1;
register char ch = 0;
while (!isdigit(ch) && ch != '-') ch = getchar();
if (ch == '-') w = -1, ch = getchar();
while (isdigit(ch)) data = 10 * data + ch - '0', ch = getchar();
return w * data;
}
const int MAX_N = 1e6 + 5;
struct Graph { int to, next; } e[MAX_N << 1];
int fir[MAX_N], e_cnt;
void clearGraph() { memset(fir, -1, sizeof(fir)); e_cnt = 0; }
void Add_Edge(int u, int v) { e[e_cnt] = (Graph){v, fir[u]}, fir[u] = e_cnt++; }
int N, K, deg[MAX_N], ans;
int dfs(int x, int fa) {
if (deg[x] == 1) return 1;
int res = 0;
for (int i = fir[x]; ~i; i = e[i].next) {
int v = e[i].to; if (v == fa) continue;
int tmp = dfs(v, x);
if (tmp + res > K) ans++, res = min(res, tmp);
else res = max(res, tmp);
}
return res ? res + 1 : 0;
}
int main () {
#ifndef ONLINE_JUDGE
freopen("cpp.in", "r", stdin);
#endif
clearGraph();
N = gi(), K = gi();
for (int i = 1; i < N; i++) {
int u = gi(), v = gi();
Add_Edge(u, v), Add_Edge(v, u);
deg[u]++, deg[v]++;
}
for (int i = 1; i <= N; i++)
if (deg[i] != 1) return printf("%d\n", (bool)(dfs(i, 0)) + ans) & 0;
return 0;
}
最新文章
- 基于Netty4的HttpServer和HttpClient的简单实现
- CSS Margin外边距合并
- 只有一个Service或Broadcast Reciver的android应用
- MongoDB 3.0.6的主,从,仲裁节点搭建
- 数往知来 ADO.NET <;八>;
- TFS 安装与管理
- <;转>;十分钟学会javascript
- vb mid 函数使用说明
- NG2入门 - 根模块
- 设置border属性变化不同形状:三角形、圆形、弧形 2017-03-20
- JS中的异步以及事件轮询机制
- freemarker写select组件(四)
- (译文)掌握JavaScript基础--理解this关键字的新思路
- obj-c编程12:复制对象
- javascript事件之调整大小(resize)事件
- NOIP-数字反转
- Linux防火墙基础与编写防火墙规则
- Apache HTTP Server应用的几个场景
- 【一步步学OpenGL 21】 -《聚光灯光源》
- 批量启动application pool
热门文章
- Java NIO , AIO
- element-UI级联选择器(Cascader)获取label值 ,this.$refs[&#39;新组件名&#39;].currentLabels 在2.7版本给移除了,新的解决方法。
- Java IO---字节流和字符流
- js学习之数据结构和算法
- Java深入学习(2):并发队列
- 025:为什么需要将Logger对象声明为private static final类型的
- Apache Kafka是数据库吗?
- FastJson--阿里开源的速度最快的Json和对象转换工具 https://www.cnblogs.com/kaituorensheng/p/8082631.html
- rsync异常处理
- OSPF 多区域配置