10.31 联测

早读，但是开始复习大联盟。

A

盲猜一波，图合法当且仅当图联通，两边对称，对角线为零。

发现这样会漏判一些不合法，跑一遍 checker 特判一下即可。

傻逼 checker 浪费我 30min。

B

设 $f_{i,j,k}$ 表示当前在是第 $i$ 分钟，摸过 $j$ 分钟鱼，上一次摸鱼在 $i-k$ 分钟。

转移大概是分下一分钟摸不摸鱼，以及把上一个作业的信息继承。

时间复杂度大概是 $O(nq\frac qT T)$，很能过啊。

C

赛时不会。

貌似和 CTSC2018 暴力写挂 是一个 trick。

把询问挂在第一颗树上，并对第一棵树边分治。

设当前分治的边为 $e$，处理的询问为 $(u,v)$。

$u,x$ 分别在边的两侧，设 $x\in S$。

则 $ans=\max_x \{d_u+w_e+d_x+dist_2(x,v)\}$。

两边配平一下 $ans=\max_x \{d_u-d_v+w_e+(d_v+d_x+dist_2(v,x))\}$。

括号外面是一个定值，括号里面是定点到点集的最大距离的形式。

可以建虚树，但是还有一个更聪明的办法。

结论：找到点集 $S$ 在第二棵树上的直径，设为 $(U,V)$，则 $x\in \{U,V\}$。

证明：和树的直径证明类似，在端点处加上 $d_x$ 没有本质区别。

所以找到 $S$ 中的直径后，用 $d_U+dist_2(v,U),d_V+dist_2(v,V)$ 中的较大值更新答案即可。

使用 $O(n\log n)-O(1)$ lca，可以做到 $O(n\log n)$。

D

挺好的一题，代码先咕着。

记 $i$ 后面第一个满足 $p_j>p_i$ 的 $j$ 为 $nxt_i$。

如果当前在 $i$，且目的地 $j \ge nxt_i$，显然 $nxt_i$ 是一定会被到达的（无论使用哪种操作）。

由于 $i$ 到 $nxt_i$ 不一定使用 2 操作。所以，预处理 $f_i$ 表示 $i$ 走到 $nxt_i$ 的最小代价。

把每个 $[i,nxt_i)$ 画出来，形成的区间要么相交，要么包含。

套路的建出一颗 $n$ 个节点的树，节点 $u$ 表示区间 $[u,nxt_u)$。

我们要求 $cost(x,y)$ 表示 $x$ 到 $y$ 的最小代价，考虑树上哪些点会产生贡献。

套用一下讲题人的图。

根据图片不难用树上前缀和维护。