[Notes] 套路/结论鉴赏

\(\text{Information on Tree}\) 树上信息

套路

• 颜色种类数：优先考虑通过变化量转换为可差分信息，其次考虑 LCT 或树链剖分套 ODT 处理树上颜色段问题。
  • 变化量：[NOI 模拟] 送你一棵圣诞树
  • LCT：[SDOI2017] 树点涂色
  • 边信息转化为点信息：[NOI2021] 轻重边
• 无边权动态直径：维护每个连通块内直径两端点 \((x_i,y_i)\)，合并时新的直径有且仅有六种情况为 \((x_i,y_i),(x_j,y_j),(x_i,x_j),(x_i,y_j),(y_i,x_j),(y_i,y_j)\)。
  • 线段树分治维护无边权的动态直径：[十连赛 Day2] 越野赛车Dash Speed
• 树链交点：若两树链相交，则两两端点的 \(\text{LCA}\) 中的最低者必为一交点。
  • 线段树维护树链合并：[HNOI2016] 网络
• distance 树分块：遍历整棵树，从下往上贪心按距离分块，\(O(\sqrt{n})\) 处理出块内距离信息。
  • 树分块维护双树祖先链信息：[NOI 模拟] 樟树

结论

• 导出子图完美匹配：对于一棵有根树点集的子集 \(S\)，设满足子树内存在奇数个属于 \(S\) 的点的结点数量为 \(t\)，显然有 \(\lceil\dfrac{|S|}{2}\rceil\leq t\)，该式等号成立构成 \(S\) 的导出子图存在完美匹配的充要条件。
  • 导出子图完美匹配快速判定：Perfect Suika Game on a Tree

\(\text{Problems Based on Sorting}\) 以排序为背景的题目

套路

• 逆序对数量变化：一定要关注逆序对数量。
  • 逆序对数量参与势能分析：CF1830E Bully Sort
  • 单个元素相关的逆序对数量在排序前后的关系：CF1677D Tokitsukaze and Permutations
• 单轮冒泡排序：前缀最值。
  • 状态记录前缀最值用以方案数量转移：[ARC187C] 1 Loop Bubble Sort