大力树剖！

前期资源来自@[ABlyh](https://www.luogu.com.cn/user/240400)同学，非常感谢！ 我很咕唉，whk和OI太忙了/kk 下面是题目链接及简单介绍： ------------ 这些都是板子 - [P3384 【模板】轻重链剖分/树链剖分](https://www.luogu.com.cn/problem/P3384) - [P4092 [HEOI2016/TJOI2016]树](https://www.luogu.com.cn/problem/P4092) - [P6098 [USACO19FEB]Cow Land G](https://www.luogu.com.cn/problem/P6098) - [P4116 Qtree3](https://www.luogu.com.cn/problem/P4116) - [P2982 [USACO10FEB]Slowing down G](https://www.luogu.com.cn/problem/P2982) - [P4315 月下“毛景树”](https://www.luogu.com.cn/problem/P4315) - [P3950 部落冲突](https://www.luogu.com.cn/problem/P3950) - [P2146 [NOI2015] 软件包管理器](https://www.luogu.com.cn/problem/P2146) - [P5903 【模板】树上 k 级祖先](https://www.luogu.com.cn/problem/P5903) ------------ ## 从这里开始下面这些稍有难度了，谨慎食用！欢迎神犇踩爆题目吊打我！ 有一些是线段树维护起来比较麻烦，码量也较大。还有一些是有一定的思维难度。（P1505码量题，欢迎挑战） - [P5838 [USACO19DEC]Milk Visits G](https://www.luogu.com.cn/problem/P5838) - [P4180 [BJWC2010]严格次小生成树](https://www.luogu.com.cn/problem/P4180) - [P4374 [USACO18OPEN]Disruption P](https://www.luogu.com.cn/problem/P4374) - [P3925 aaa被续](https://www.luogu.com.cn/problem/P3925) - [P4616 [COCI2017-2018#5] Pictionary](https://www.luogu.com.cn/problem/P4616) - [CF1023F Mobile Phone Network](https://www.luogu.com.cn/problem/CF1023F) - [P4211 [LNOI2014]LCA](https://www.luogu.com.cn/problem/P4211) - [P5305 [GXOI/GZOI2019]旧词](https://www.luogu.com.cn/problem/P5305)（上面一题的加强版，好题！） - [P6157 有趣的游戏](https://www.luogu.com.cn/problem/P6157) - [P4332 [SHOI2014]三叉神经树](https://www.luogu.com.cn/problem/P4332) - [SP16549 QTREE6 - Query on a tree VI](https://www.luogu.com.cn/problem/SP16549) - [P1505 [国家集训队]旅游](https://www.luogu.com.cn/problem/P1505) ------------ 对于某些题目，上跳过程中，维护两边目前已经跳过的部分的信息是常见手段，每次查询到当前段的信息和原有信息合并规则往往和线段树区间信息合并规则一致。 - [P2486 [SDOI2011]染色](https://www.luogu.com.cn/problem/P2486) - [SP6779 GSS7 - Can you answer these queries VII](https://www.luogu.com.cn/problem/SP6779) - [P3976 [TJOI2015]旅游](https://www.luogu.com.cn/problem/P3976) - [P7735 [NOI2021] 轻重边](https://www.luogu.com.cn/problem/P7735) （需要十分巧妙的转化） ------------ 涉及了换根操作。可别真换！提示一下，要根据当前树根以及当前查询的节点的位置关系展开分类讨论，转化为以 $1$ 为根的问题！ - [CF916E Jamie and Tree](https://www.luogu.com.cn/problem/CF916E) - [P3979 遥远的国度](https://www.luogu.com.cn/problem/P3979) ------------ 树剖套动态开点线段树 - [P3313 [SDOI2014]旅行](https://www.luogu.com.cn/problem/P3313) ------------ 树剖套主席树 - [P4216 [SCOI2015]情报传递](https://www.luogu.com.cn/problem/P4216) ------------ 圆方树上树剖 - [P4320 道路相遇](https://www.luogu.com.cn/problem/P4320) - [CF487E Tourists](https://www.luogu.com.cn/problem/CF487E) ------------ 树剖套线段树套线性基（其实我也不知道该不该单独拿出来当做一类） - [P3292 [SCOI2016]幸运数字](https://www.luogu.com.cn/problem/P3292) ------------ 下面是 ddp！~~其实我今天刚学会，好菜呜呜呜~~ - [P4719 【模板】"动态 DP"&动态树分治](https://www.luogu.com.cn/problem/P4719) - [P4751 【模板】"动态DP"&动态树分治（加强版）](https://www.luogu.com.cn/problem/P4751)（PS：你不是卡树剖嘛？我树剖过给你看！但是需要较快的 IO 和常数优化，比如矩阵乘法直接手写不要循环，再比如对于每条重链分别单独开线段树） - [P5024 [NOIP2018 提高组] 保卫王国](https://www.luogu.com.cn/problem/P5024)