今日份收获是什么呢？两个做法阈值分值，增量维护路径，保证一步控制，外部乘兄弟的换根，以及早睡晚起可以逃一次早自习（划掉）。
感知了一下，交互这一块反而像二分这样的东西用得少一点，增量这种更多，因为信息更密集，当然明显的对数还是不要犯唐了。
CF750F
一开始想直接 bfs，但这个只有初始点深度比较小才对。
要是随到一个深度大的呢？考虑一下发现可以 dfs，找出一条链，然后中点是 LCA，也就是最上方的点。
理性分析一下，dfs 代价近似为当前深度的两倍，但也排除了等深度的，不过更低层的深度会重复叠加一点，就导致超了一些。
怎么办呢？因为我们知道深度，所以可以按照深度分治，跑到浅层点之后把上面那个 bfs 缝进来。
其实这个时候还是会超一个，但我们知道如果我们问了可能集合的其他点都不是，剩下的一个就一定是，不用再问了。
如果一开始 dfs 写成“精细讨论一次一层”，会很石，但直接跳 LCA 就好多了，比较难蚌。
P9601
暴力把图问出来，肯定能做完。
手玩一下发现答案长度貌似是最大的一个连通块，进一步可以发现最多两个连通块，而且两个连通块下是两个团。
本来想随便写写把块划分出来就能过，然后发现要方案，摆了。
正解做法是基于维护路径的扩展，因为有两个连通块，所以可以一次维护两条路径出来，如果实际是一个块的话可以拼出来。
一个显然的 \(2n-4\) 维护路径是每次加一个点，要么发现两条路径可以合并，要么发现可以加进其中一条路径，如果你固执地维护了一个路径就会似在这里。
后面的拼接比较容易，就是考虑首尾啥的，然后首尾拼不上可以发现这是个环，二分前缀来找边断开。
问题在于前面这个部分超了大概 \(n/2\) 次，这启发我们 \(2n\to 1.5n\)。
这种砍半的常见思路是两次一个点改三次两个点，讨论一下发现是可行的。
ARC146D
要满足一堆限制，感觉像建图，每个点加 \(m\) 个变量 \(x_{i,j}\) 表示是否 \(a_i\le j\)。
把中间一些奇奇怪怪的东西离散化掉，再改个 \(\ge\) 做一遍，感觉能跑 2-sat 状物啊。
这个方法是对的，但是为啥你们的代码这么简洁？
原来是一种神秘增量贪心构造做法，无敌了。
考虑把限制拆成 \((a_p\ge x\Leftrightarrow a_q\ge y)\wedge(a_p\ge x-1\Leftrightarrow a_q\ge y-1)\)，这样可以都化成一个形式，方便得多。
一种贪心是每次把 \(a_p\ge x\) 的拉出来更新 \(a_q\gets\max(a_q,y)\)，然后再到 \(a_q\) 上面找。
显然我们一个限制不应考虑两次，那这就套个当前弧，然后写个 bfs 状物，当满足完所有限制的时候就结束了。
QOJ14306
围堵小猫问题的经典策略是外面修一圈墙，但显然你修得没有小猫跑得快，这个时候有个想法就是偷工减料，空一格修一个（保证能一步控制），这样只需在小猫接近的时候堵上就行了（好残忍/jk/jk/jk）。
但是先修哪侧也是个问题，一个简单的想法是哪侧离墙近就先修哪侧，但这样是不对的，小猫可能来个急速拐弯坑杀你。
但只需先把右上角修出来就好了，这步比较神……剩下的就是简单二分了。
QOJ14324
本来想上个 poly inv 力大砖飞，但是 TLE。
考虑正经一点的换根，容易发现我们每个点外部这一块只需保留它子树大小。
考虑我们把父亲那一块只保留自己子树大小这样来乘进来，兄弟的用前后缀乘积的形式乘进来。
这样看兄弟那一块和原来树形 dp 一样是 \(\mathcal{O}(n^2)\) 的，而父亲乘进来这一步看起来是整体 \(\mathcal{O}(n^3)\)。
但其实是对的，因为乘父亲这一步实际上是外部乘兄弟，这个东西我不太会分析，但容易发现传统的一些链或者二叉树啥的是没办法卡的。