22acm训练:树
22acm训练:树
知识点
树的dfs序列有哪几种?分别有什么性质?
最近公共祖先的求法 (至少掌握倍增,此外树上倍增也是部分题目的优雅解法)
树上差分: 边差分和点差分
子树信息维护 类换根信息维护
树的直径:两次dfs求法 dp求法
作业
这次的题目都比较板,供大家学习
如有困难,请参看洛谷的题解页面
https://www.luogu.com.cn/problem/P5536
https://www.luogu.com.cn/problem/P3128
https://www.luogu.com.cn/problem/P1351
https://www.luogu.com.cn/problem/P3178
https://codeforces.com/problemset/problem/877/E
https://www.luogu.com.cn/problem/P4116 [数据结构专精同学选做]
https://ac.nowcoder.com/acm/contest/22131/C [数据结构专精选手选做]
作业2
https://www.acwing.com/problem/content/354/
https://www.luogu.com.cn/problem/P1099
https://www.luogu.com.cn/problem/P3398
https://www.luogu.com.cn/problem/P2680
https://www.luogu.com.cn/problem/P5588
https://www.luogu.com.cn/problem/P4719(了解即可)
作业3
涉及到一些树和图上的转移和统计,一些简单的tricks. https://www.luogu.com.cn/problem/P1608
https://www.luogu.com.cn/problem/CF1209D
https://www.luogu.com.cn/problem/P3478
快手开奖63人在聊