『应用（折磨）篇』重链剖分

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