重链剖分学习笔记 by lzy
『从入门到入土』树链剖分学习笔记 by Hoks
Part 2.
P9997 为 CF1045J 的加强版！
目前
个人进度
蒟蒻也要努力成为树剖出锅魔怔人
如果出锅了可以对着查下（虽然可能不是同种锅。
P9808 [POI2022~2023R1] zbo：式子拆开就做完了。
Xenia and Tree：有
GOT - Gao on a tree：同上题。
[ABC133F] Colorful Tree：同上题，多维护一个每种颜色数量。
Answering Queries on a Tree：同上题，但是因为颜色少直接暴力枚举颜色对每种颜色取
Santa's Gift：推完式子就又变成上面那个套路了。
Caisa and Tree：类似上面的套路，对每种质因数开线段树即可。
P4947 PION后缀自动机：同上题，对字符串离散化即可。
GSS7 - Can you answer these queries VII：用树剖直接把最大子段和扔到树上。
P7735 [NOI2021] 轻重边：神仙转化后线段树维护方式类似上题。
P5478 [BJOI2015] 骑士的旅行：把
Duff in the Army：路径前
P9555 「CROI · R1」浣熊的阴阳鱼：把鱼框的信息扔进线段树里维护。
P4679 [ZJOI2011] 道馆之战：因为二维，所以线段树的
P2486 [SDOI2011] 染色：轻重边 的双倍经验。
P4312 [COI2009] OTOCI 和 OTOCI - OTOCI：离线，用树剖维护森林，连通性用并查集。
P2542 [AHOI2005] 航线规划：离线，倒序加边，成环就赋
P4211 [LNOI2014] LCA：推式子入门题。
Tavas on the Path：毒瘤题，把边排序后扔到线段树上处理信息。
Drivers Dissatisfaction：经典 trick，通过路径查询最大值替换的方法实现一个类动态 MST。
Best Edge Weight：类似于上题的做法。
Misha and LCP on Tree：经典 trick，树剖维护 hash，能整链跳的整链跳，不能的二分找断点。
P1600 [NOIP2016 提高组] 天天爱跑步：对每种深度的点开线段树大力做。
Dynamic Diameter：考虑大力做法，两颗线段树，一个维护到根距离，一个维护直径。
P4556 [Vani有约会] 雨天的尾巴：权值线段树，拆开修改区间。
...Wait for it...：毒瘤题，拆点算答案。
P3979 遥远的国度：换根树剖，分类讨论即可。
P3976 [TJOI2015] 旅游：这个应该算是线段树 trick 了，利用左右区间一定单调的性质。
Jamie and Tree：同 P3979。
Tree or not Tree：考虑经典 trick，给环剥下来缩成点，然后新树和环各一颗线段树维护。
Tourists：建圆方树，树剖维护即可。
Mobile Phone Network：和前面那些 MST 的题一样。
P3250 [HNOI2016] 网络：树剖套堆大力维护。
P3676 小清新数据结构题：推式子换根即可。
P3925 aaa被续：略转化扔树剖即可。
P3995 树链剖分：友情客串。
P4115 Qtree4：把树剖类似于边分治看。
P4175 [CTSC2008] 网络管理：树剖套树状数组套主席树。
P6805 [CEOI2020] 春季大扫除：简单 trick 转化为树剖板子题。
P4592 [TJOI2018] 异或：树剖+可持久化 trie。
Two-Paths：换根 dp 还有套树剖修改，也是够折磨的。
Alphabetic Tree：毒瘤题，本质还是树剖把 hash 上树，但是需要神仙优化。
Noble Knight's Path：树剖+可持久化线段树，整链直接跳，不然二分。
Moonwalk challenge：毒瘤题，还是树剖+hash，但要分类讨论，还要在 vector 里二分。
P5138 fibonacci：用斐波那契数列的经典结论把修改拆开正常维护即可。
P9997 [Ynoi2000] pmpkmp：Moonwalk challenge 的加强版，因为带修所以要更多神仙的技巧。
P4338 [ZJOI2018] 历史：神仙分讨转化为简单维护题。