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

Part 2. 感谢神犇 skz 给的两道题。 [Edges in MST](https://www.luogu.com.cn/problem/CF160D) 和 [Daleks' Invasion (hard)](https://www.luogu.com.cn/problem/CF1184E3)：还是树剖+MST 的套路。 [P3703 [SDOI2017] 树点涂色](https://www.luogu.com.cn/problem/P3703)：因为颜色均摊段，所以暴力区间合并复杂度是对的。 [P4216 [SCOI2015] 情报传递](https://www.luogu.com.cn/problem/P4216)：离线转化变为板子。 [P5499 [LnOI2019] Abbi并不想研学](https://www.luogu.com.cn/problem/P5499)：每个点维护集合，每个链顶维护链。 [P5305 [GXOI/GZOI2019] 旧词](https://www.luogu.com.cn/problem/P5305)：找完性质就变回了[P4211 [LNOI2014] LCA](https://www.luogu.com.cn/problem/P4211)，难怪叫旧词。 [P5559 失昼城的守星使](https://www.luogu.com.cn/problem/P5559)：写式子，拆式子，然后就做完了。 [P7671 [GDOI2016] 疯狂动物城](https://www.luogu.com.cn/problem/P7671)：把题目中的式子转化拆开，但是丧心病狂的出题人非要让选手写主席树。 [P6157 有趣的游戏](https://www.luogu.com.cn/problem/P6157)：转化为链数严格第二大，实现还是有点难度。 [P5773 [JSOI2016] 轻重路径](https://www.luogu.com.cn/problem/P5773)：离线，跳链+二分。 [P5556 圣剑护符](https://www.luogu.com.cn/problem/P5556)：树剖+线性基（但我不会）。 [P4719 【模板】"动态 DP"&动态树分治](https://www.luogu.com.cn/problem/P4719) 和 [P4751 【模板】"动态DP"&动态树分治（加强版）](https://www.luogu.com.cn/problem/P4751)：ddp 入门题，用线段树在链顶维护这条链的矩阵来 dp。 [P5024 [NOIP2018 提高组] 保卫王国](https://www.luogu.com.cn/problem/P5024)：把上一题的最大小值颠倒一下就行。 [P8820 [CSP-S 2022] 数据传输](https://www.luogu.com.cn/problem/P8820)：毒瘤题，分讨 $k$，$k=1$ 直接做，$k=2$ 倍增 ddp，$k=3$ 树剖 ddp。 [P5391 [Cnoi2019] 青染之心](https://www.luogu.com.cn/problem/P5391)：类树剖状物的背包。 [P5558 心上秋](https://www.luogu.com.cn/problem/P5558)：值域很小，直接把这个信息打包进线段树维护。 [P6021 洪水](https://www.luogu.com.cn/problem/P6021)：构造转移方程式，依旧 ddp。 [QTREE4 - Query on a tree IV](https://www.luogu.com.cn/problem/SP2666) 和 [P2056 [ZJOI2007] 捉迷藏](https://www.luogu.com.cn/problem/P2056)：同上个题单的 Qtree4。 [P2633 Count on a tree](https://www.luogu.com.cn/problem/P2633)：大力树剖套主席树。 [P3320 [SDOI2015] 寻宝游戏](https://www.luogu.com.cn/problem/P3320) 和 [Archaeology](https://www.luogu.com.cn/problem/CF176E)：线段树分治后上树剖草。 [Choosing Subtree is Fun](https://www.luogu.com.cn/problem/CF372D)：转化题意直接无脑树剖维护。 [P9399 「DBOI」Round 1 人生如树](https://www.luogu.com.cn/problem/P9399)：树剖维护 hash，轻松拿下最优解。 [Arkady and a Nobody-men](https://www.luogu.com.cn/problem/CF860E)：重剖直接大力拆式子维护，但是长剖好像珂以线性？ [Colored Tree](https://www.luogu.com.cn/problem/CF1260F)：拆式子维护就行了，但貌似不是很好写。 [Tree Queries](https://www.luogu.com.cn/problem/CF1254D)：毒瘤题，树剖后根号分治，然后分讨用分块维护。 [Middle Duplication](https://www.luogu.com.cn/problem/CF1623E)：树剖维护字符串，大力推平维护。 [P9620 歌姬](https://www.luogu.com.cn/problem/P9620)：转化下题意，直接树剖维护。 [[ABC351G] Hash on Tree](https://www.luogu.com.cn/problem/AT_abc351_g)：ddp，但是注意修改为 $0$ 是乘积可能会炸。 [The Number Games](https://www.luogu.com.cn/problem/CF980E)：小贪心，树剖大力维护即可。 [P4069 [SDOI2016] 游戏](https://www.luogu.com.cn/problem/P4069)：树剖套李超树。 [P5354 [Ynoi2017] 由乃的 OJ](https://www.luogu.com.cn/problem/P5354)：把信息合起来在线段树里处理。 [P10599 BZOJ2164 采矿](https://www.luogu.com.cn/problem/P10599)：ddp 维护即可。 [P10626 [JOI Open 2024] 考试 2](https://www.luogu.com.cn/problem/P10626)：表达式树，类 ddp 的维护法。 [P11295 [NOISG2022 Qualification] Dragonfly](https://www.luogu.com.cn/problem/P11295)：势能线段树然后扔个 BIT 维护前缀和就行了。 [P3781 [SDOI2017] 切树游戏](https://www.luogu.com.cn/problem/P3781)：FWT，然后再上 ddp。 [P5642 人造情感（emotion）](https://www.luogu.com.cn/problem/P5642)：毒瘤题，树剖+神仙优化。 [P8334 [ZJOI2022] 深搜](https://www.luogu.com.cn/problem/P8334)：推式子，扫描线，ddp+神仙优化为单 $\log$。 [P8959 「CGOI-3」灵气](https://www.luogu.com.cn/problem/P8959)：转化题意，对连通块树剖维护。 [P5314 [Ynoi2011] ODT](https://www.luogu.com.cn/problem/P5314)：树剖+平衡树硬卡。 [瓦里奥世界 Rujia Liu loves Wario Land!](https://www.luogu.com.cn/problem/UVA11998)：阴间题，启发式合并树剖，因为要支持重构所以要用分块维护。 [P10574 [JRKSJ R8] 暴风雪](https://www.luogu.com.cn/problem/P10574)：根号分治两次+树剖。 [Can Bash Save the Day?](https://www.luogu.com.cn/problem/CF757G)：树剖+主席树+神仙合并。 [P8353](https://www.luogu.com.cn/problem/P8353)：我是卡空间大蛇（）。