CF2134F
和 的极长连续段分别考虑，段内代价为 ，段间为 。
对 再考虑 和 的极长连续段，段间代价为 。枚举分别有 段，段间切 下，段内切 下，就得到 形成 个极长连续段的方案数。
P4298
给定一个 DAG，构造最长反链。
传递闭包求出偏序关系。最长反链等于最小链覆盖。
求最小链覆盖，网络流，拆点，如果存在 ，连边 ，求二分图最大匹配。
从 出发走 的边 dfs。左部点能去到的加右部点不能去到的是最小点覆盖。补集，即左部点不能去到的加右部点能去到的是最大独立集。
和 同时属于最大独立集的 是 DAG 的最长反链。
CF590E
ACAM 上，路径压缩跳 fail 树祖先中最近的终止节点，再传递闭包求出两两串的子串关系。
是偏序集，求最长反链。
0910
Q5020
树剖，把答案拆为子树内/轻子树内距离 的点的数量。
离线后二位数点。。
P5470
由于模型的特殊，于 相连的边不会退流。
建图后能说明本质不同的有意义的增广路只有 类。堆维护。
abc363g
可以以一个任意的顺序加入 ，维护流量变化，线段树分治回答修改。
可能的情况是负环或 的负权路径。
需要一个线段树维护流量，一个线段树维护可能被退流的最小值。
AT_nikkei2019_final_h
不会有负环。增广路不会经过重复的点。直接求增广路，有很多个可以用线段树 pushup 维护的限制。
Q5175
到关键点的最短路形成外向树。类似斯坦纳树，设 表示覆盖 的关键点，升级 条边，当前树根为 。
转移为同层的最短路和枚举子集合并。枚举子集时 有单调性。
0916
0917
P13275
题解。
P10547
最后代价为 。由势能 代价至少这么多，一定存在 代价至多这么多。
数 即 abc134f，考虑跨过 时计算贡献，且最多 个跨过贡献，复杂度 。
合法的新排列要求置换环为偶数：从 个置换环出发，每交换 置换环奇偶性变化。
对应到置换环上，设 ，前 个点 个 的 未决定，代价为 ， 个置换环。可以：新开链/环，拓展链，封闭链，合并链。
0926
CF1942G
抽到 牌减 ， 牌无用， 牌加 。目标牌当做 牌。
初始 张 牌，从 出发，除了最后一次以外不碰 ，的方案数。
枚举最后用了 张 牌，反射容斥求出恰好抽掉这些牌的合法方案数，再 选出目标牌，后面乱选。
CF1942H
厉害。
和 做二分图匹配，要求每个 都能被 匹配到。 能匹配儿子和祖先的 ， 能匹配子树和祖先的 。
hall 定理，要求 。设 表示考虑 子树， 出在 中， 子树有没有全被选入 。
-
同时不选 ， 可以选择一些子树转移，。
-
选 不选 ， 必须从全部儿子转移，。
-
不选 选 ， 的覆盖范围被 偏序，多选上 有 的贡献。
-
同时选 ，此时 子树全被选入 ，.
修改形如单点修改 ，ddp 维护 。
CF2096G
维护 个三进制数，使得每位都有 两个值 出现次数相同，且任意两个数至少有两位不同。
前 位均分着填，最后一位按之前的位的和模 。
CF2097F
题解。
CF2115E
题解。
CF2122F
一个矩形，上边界 个点，下边界 个点，可以凑出组合数 。
多个矩形可以用一个狭窄的部分连起来，要保证连接部分剖分唯一。
分治乘控制点数。
CF2138E2
here。