Day 57 - 11.1
CSP 拉了一地啊，非常的不好，T2想了一圈想了几百年才想到 Floyd
1.P17833 [CSP-S 2026] 迁徙 / migrate
一种做法是考虑根据两条路径至多有一个位置不一样，并且那个位置两条路径中一定相邻来计数，但这个太难了
考虑显然最短路径显然不会向左飞，于是枚举左端点 \(l\) 后定义 \(f_i\) 表示从 \(l\) 到 \(i\) 的最短路径条数，显然 \(f_i=\sum\limits_{x_i-x_j\le d \land \operatorname{dis}(l,j)+1=\operatorname{dis}(l,i)} f_j\)，合法右端点有 \(f_i=2\)，这个东西是 \(O(n^3)\)
发现如果一个点的 \(f_i>2\)，那么这个点就废了，不管怎么往后走路径只会越来越多，因此先把 \(f_i\ge 3\) 给砍了，其次我们发现对于 \(f_i\ne 0\) 的点，前面能到的后面肯定也能到，因此对于每一层只关心最靠后且 \(f_i\ne 0\) 的三个点即可
于是考虑 \(\operatorname{dp\;of\;dp}\)，定义 \(dp_{i,x,y,z}\) 表示当前层最靠右的点是 \(i\)，且当前层最靠右的三个点的 \(f\) 值分别为 \(x,y,z\) 时，在当前状态下有几个合法的右端点
转移时考虑预处理 \(R_i\) 表示从 \(i\) 开始下一步最远跳到哪个点即可，由于 \(x\in\{0,1\},y\in\{0,1,2\},z\in\{0,1,2,3\}\)，状态数非常少，最终答案为 \(\sum_{i=1}^n dp_{i,0,0,1}\)，时间复杂度 \(O(n)\)
2.P17834 [CSP-S 2026] 研发基地 / hub
显然先二分转为判定性问题，设当前二分值为 \(r\)
考虑先对原树进行 \(r\) 轮删叶子操作，剩下的部分记为 \(C\)，显然若 \(|C|\le k\) 直接可行，否则选点可以只在 \(C\) 中进行
显然 \(C\) 中的核心叶子，即悬挂部分最大深度超过 \(r\) 的叶子和度数 \(\ge 3\) 的分叉点均必选，显然把这两种点排除后 \(C\) 中的未选点只会出现在度数为 \(2\) 的链上，并且该缺口必须是连续的一段，转化为在 \(C\) 的每条二度链上能否连续删去 \(D=|C|-k\) 的点，使得剩下的点仍能在 \(r\) 的半径下覆盖整棵树
对链上的每个点预处理 \(h_i\) 表示从 \(i\) 向链外延伸的最大悬挂深度，设 \(b_i=r-h_i\)，链上删除的连续区间为 \([L+1,L+D]\)，有 \(\min(i-L,L+D+1-i)\le b_i\)，显然若 \(b_i<0\) 则所有 \(L\) 不合法，\(b_i\ge 0\) 则有 \(i+b_i-D\le L，考虑用差分维护该禁用区间
发现这样做需要在每条链上快速判断一个点是否在链内以及它的悬挂深度 \(h_i\)，这无疑是会 T 掉的，预处理每个点所有邻居的删叶时间的前三大值 \(t_1\ge t_2\ge t_3\)，可以 \(O(1)\) 判断该点是否在链内并直接得到它的悬挂深度，所有链的总长度为 \(O(n)\)，因此每个 check 是 \(O(n)\) 的，总复杂度 \(O(n\log n)\)
Day 58 - 11.2
又是模拟赛……