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

https://www.luogu.com.cn/problem/P2016

http://codeforces.com/problemset/problem/1304/E

全部评论

相关推荐

不愿透露姓名的神秘牛友
06-19 17:02
鼠鼠深知pdd的强度很大,但是现在没有大厂offer,只有一些不知名小厂我是拒绝等秋招呢,还是接下?求大家帮忙判断一下!
水中水之下水道的鼠鼠:接了再说,不图转正的话混个实习经历也不错
投递拼多多集团-PDD等公司10个岗位 >
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务