migrate

被击杀了。赛时一直在想什么怎么刻画出具体的合法路径形态，转化成了 \(x\) 可达 \(x-1\) 可达但 \(x-2\) 不可达之类奇异搞笑的形态，也没有认真思考 DAG 上的 dp 能不能优化，最后暴力遗憾离场。

Sol.1

令 \(R(u)\) 表示位置 \(u\) 往右跳能够跳到的最远位置，那么不断跳 \(R(u)\) 到达 \(v\) 就是 \(u\leadsto v(u 的一条最短路，记这样跳出的路径为 \(u=x_0\to x_1\to\dots\to x_k\to x_{k+1}=v\)。由于要分析最短路数量，我们可以贪心的寻找一条路径的下界，每次跳一个能够以最短路抵达终点的最靠左的位置跳过去，不难发现这就相当于从 \(v\) 出发，每次选择能跳到的最左位置，记 \(L(u)\) 表示这个位置，可以得到另一条路径 \(u=y_0\to y_1\to\dots\to y_k\to y_{k+1}=v\)。令 \(I_i=[y_i,x_i]\)，我们声称 \(u\leadsto v\) 的最短路恰好有 \(2\) 条等价于：恰好存在一个 \(i\) 满足 \(|I_i|=2\)，其余位置均满足 \(|I_i|=1\)。也就是正反分别贪心，这两条路径有且仅有一个位置不同，且位置差恰好为 \(1\)。若存在 \(|I_i|\ge 3\)，由于这个区间中任意位置都可以拉出一条最短路，不合法； 若存在 \(|I_i|,|I_j|=2\)，可以通过选择错位的两个位置再拉一条最短路出来。

得到这个形态就很容易计数了。枚举中间这个不同的位置 \(w\)，不难发现左右部分是独立的。以左半边为例，需要满足 \(R(L(w))=w+1\)，令 \(\mathrm{cntR}_i\) 表示 \(R(x)=i\) 的个数，\(f_i\) 表示以 \(i\) 结尾的合法链数量，得到递推 \(f_i=[R(L(i))=i]f_{L(i)}+\mathrm{cntR}_i\)，右边同理。时间复杂度线性。

Sol.2

考虑固定住起点怎么计算答案，我们有最短路条数的转移：

\[g_i=\sum\limits_{x_j\in [x_i-d,x_i)\wedge d_i=d_j+1} g_j \]

考虑找一下图的性质，我们发现，最短路相同的点构成了一个区间。那么起点往后的位置可以被分成若干层，形如 \([\dots,r],(r,R(r)],(R(r),R(R(r))]\)，那么这个最短路 dp 其实就是当前层的每个位置向下一层的某个前缀转移。

由于我们只关注 \(g_i\le 2\) 的状态，\(g_i>2\) 的状态可以统一压成 \(3\)。于是得到关键性质：只需要保留当前层最后三个位置进行转移。因此我们设 \(f_{i,x,y,z}\) 表示当前结尾为 \(i\)，末尾三个数顺次为 \((x,y,z)\) 时，往后走的过程中 \([g_k=2]\) 的位置个数。答案就是 \(\sum_{i=1}^n f_{i,0,0,1}\)。

hub

其实不难，赛时没有做到抽出足够时间看每道题。失策。

显然二分答案为 \(mid\)。考虑只有一个连通块怎么做。从下往上贪心，对于树上连通块我们只关注最高点的深度，记 \((\mathrm{siz},\mathrm{dep})\) 表示子树中构造出的点数最小的连通块大小为 \(\mathrm{siz}\)，最高点到当前子树根的距离为 \(\mathrm{dep}\)。

  • 若两个子树中都没有连通块，判断 \(\max(\mathrm{dep}_x,\mathrm{dep}_y)\) 与 \(mid\) 的关系来决定是否激活子树根。
  • 若两个子树都有连通块，将其与子树根连通即可。
  • 若一个子树内有连通块，另一个没有。考察没有连通块的子树内最深点的限制，若 \(\mathrm{dep}_x+\mathrm{dep}_y\le mid\) 则限制已经满足，否则记 \(r=\mathrm{dep}_x+\mathrm{dep_y}-mid\)，需要从当前的连通块根向上延伸 \(r\) 个单位才能满足限制，推一下可以发现贡献到 \((\mathrm{siz}_x+r,\max(0,\mathrm{dep}_x-r))\)。

会做单个连通块正解就呼之欲出了，如果只选单个那么判断 \(\mathrm{siz}_1\le K\) 即可，否则两个连通块一定可以被某条边切割为子树内和子树外，子树外用换根解决即可，最后判断 \(\mathrm{siz}_{\mathrm{in}}+\mathrm{siz}_{\mathrm{out}}\le K\) 即可。单次 check 时间复杂度 \(O(n)\)，总时间复杂度 \(O(n\log n)\)，需要一定的卡常。