DAY 5 下午
2024-09-05 21:19:13
每个点一定属于一个重链
重链条数和轻边边数是logn级别
证明和启发式合并差不多
因为轻子树的大小至少是重子树大小-1
树链剖分：两遍dfs
第一次：统计子树大小，确定重儿子
第二次：把重链剖出来
每次都走重儿子，则它的dfs序中重链是连续的一段
复杂度o(log n)
改变边权和询问路径上最大边权
把边权放到点上，把点权放到线段树中
修改的时候就是单点修改
查询最大边权的时候，就查询两条链（因为lca存的是它到它父亲这一条边的边权）上的最大值
重链-轻边-重链-轻边
找线段树上对应的区间然后查询就可以
开一个2000位的bitset
第i位是1表示标号为i的bitset可以到达他
这个scc的大小*它能到达的scc的大小之和再加起来就是答案
bitset
#include<bitset>
bitset<100000> a;
表示一个长度为100000的二进制数（下标从0开始）
bitset<100000> b;
a[1]可以取到第一位
a[0]
a[99999]=1;
a&b
a^b
a|b
a.set
a.reset
a.count(数有多少1)
最新文章
- ASP.NET MVC5 网站开发实践(二) Member区域 - 文章管理架构
- mysql timeout connection
- VS工程添加资源文件
- 后台接收前台传入的json 数据
- UESTC 878 温泉旅馆 --性质+枚举
- centos7 最小化安装 无 ifconfig,netstat 的安装
- Web服务器（Apache）虚拟主机的配置
- 错误内存【读书笔记】C程序中常见的内存操作有关的典型编程错误
- python自动开发之第十八天
- 转 jquery插件--241个jquery插件—jquery插件大全
- 2015华为德州扑克入境摘要——软体project
- offsetWidth，offsetHeight到底该如何理解？
- Natas Wargame Level 3 Writeup 与 robots.txt
- 20164305 徐广皓 Exp3 免杀原理与实践
- Mockito单元测试实战
- Python制作二维码和条形码扫描器 （pyzbar）
- MySQL中间件之ProxySQL(4)：多层配置系统
- 关键字（8）：数据库记录的增删查改insert，delete，select，update
- vue项目使用element-ui的Tooltip 无效
- cleanmymacchinese下载链接