树链剖分
题单介绍
熟 练 抛 粪
# 一：模板题
- [P3384 【模板】轻重链剖分/树链剖分](https://www.luogu.com.cn/problem/P3384)
- [P3379 【模板】最近公共祖先（LCA）](https://www.luogu.com.cn/problem/P3379)
- [P3833 \[SHOI2012\]魔法树](https://www.luogu.com.cn/problem/P3833)
- [P3178 \[HAOI2015\]树上操作](https://www.luogu.com.cn/problem/P3178)
- [P3038 \[USACO11DEC\]Grass Planting G](https://www.luogu.com.cn/problem/P3038)
- [P3950 部落冲突](https://www.luogu.com.cn/problem/P3950)
目标：掌握基本的树链剖分模板，保证应用的时候不会写错
# 二：应用与变形
- [P2420 让我们异或吧](https://www.luogu.com.cn/problem/P2420)
- [P3258 \[JLOI2014\]松鼠的新家](https://www.luogu.com.cn/problem/P3258)
- [P4281 \[AHOI2008\]紧急集合 / 聚会](https://www.luogu.com.cn/problem/P4281)
- [P3128 \[USACO15DEC\]Max Flow P](https://www.luogu.com.cn/problem/P3128)
- [P2146 \[NOI2015\] 软件包管理器](https://www.luogu.com.cn/problem/P2146)
- [P4114 Qtree1](https://www.luogu.com.cn/problem/P4114)
- [P4116 Qtree3](https://www.luogu.com.cn/problem/P4116)
- [P4315 月下“毛景树”](https://www.luogu.com.cn/problem/P4315)
目标：掌握树链剖分在实际题目中的运用
# 三：换根操作
- [P3979 遥远的国度](https://www.luogu.com.cn/problem/P3979)
- [CF916E Jamie and Tree](https://www.luogu.com.cn/problem/CF916E)
- [LOJ139 树链剖分](https://loj.ac/p/139)
# 四：较难题目
- [P3401 洛谷树](https://www.luogu.com.cn/problem/P3401)：序列常见问题在树上的实现
- [P1505 \[国家集训队\]旅游](https://www.luogu.com.cn/problem/P1505)：码量巨大
- [P2486 \[SDOI2011\]染色](https://www.luogu.com.cn/problem/P2486)：套颜色段数量问题，细节多
- [P3250 \[HNOI2016\]网络](https://www.luogu.com.cn/problem/P3250)：线段树套堆？
- [P3313 \[SDOI2014\]旅行](https://www.luogu.com.cn/problem/P3313)：动态开点线段树
- [P2680 \[NOIP2015 提高组\] 运输计划](https://www.luogu.com.cn/problem/P2680)：将线段拆分维护不经过一条路径的最大权值
- [P4175 \[CTSC2008\]网络管理](https://www.luogu.com.cn/problem/P4175)：树剖套线段树套平衡树加二分答案，[四只 $\lg$ 能过](https://www.luogu.com.cn/record/66660623)！
- [P4216 \[SCOI2015\]情报传递](https://www.luogu.com.cn/problem/P4216)：主席树
- [P7735 \[NOI2021\] 轻重边](https://www.luogu.com.cn/problem/P7735)：利用两点颜色差异转化题目所给的轻重边