T1

赛时：

开局觉得 $O(n^3)$ 做法非常靠谱，枚举第一二四个点，预处理点对中两点都能到达的点的最大值次大值(防止重点)，打完 $70$ 跑路，$100$ 分的想了一个很不靠谱的需要大力分讨的 $O(n^2)$ 找五元环做法，觉得不好打，跑路了。

赛后：

发现 $O(n^3)$ 做法也假了呜呜呜。然后发现是没开ll啊靠。

解法：

事实上距离正解之差一步/(ㄒoㄒ)/~~

只需要枚举第二第三个点就好了，预处理 $1$ 与 $i$ 能够共同到达的点的最大次大次次大，然后暴力一下就做完了。复杂度 $O(n^2)$。

T2

赛时：

~~博弈论不会跳了~~，发现是个假的博弈论，只要把少数几个可能答案提取出来然后暴力即可。30min 过所有样例。

赛后：

没挂好耶ヽ(✿ﾟ▽ﾟ)ノ。

解法：

具体来说就是答案只会出现在正的最大，正的最小，负的最大，负的最小这些数中间，所以用 st 表把它们都找出来然后暴力枚举即可。为了保证正确性，加了个 $0$ 的判断。不过我懒得证了。复杂度 $O(n\log n)$，有 $10$ 倍常数。

赛时：

又臭又长的题面赶紧润。最后 30min 想着骗点分甚至没管过没过样例。

赛后：

由于代码丢了，做法又假，懒得打了。

然后重新打了一发发现完全没错，甚至拿了60pts？？！

解法：

$\rm hash$ 乱搞，不过我也不太会证正确率 QAQ。

首先图合法的充要条件是每个点出度都为 $1$。

给每个点随机赋上一个权值，然后维护一下全局点权 $\times$ 出度的和，判一下与点权和是否相等就好了。复杂度 $O(n+m+q)$。

赛时：

树！DS！这个我会！好的然后只会暴力… 但是暴力分好高！开搞，2h 把特殊性质的和 $\leq2000$ 的点搞出来过了样例，然后想怎么矩阵维护，发现我只会个板不会写/(ㄒoㄒ)/~~。

赛后：

没挂好耶ヽ(✿ﾟ▽ﾟ)ノ，(luogu 76pts)。

赛后恶补了一下矩阵维护 $dp$。

解法：

$K=1$ 随便搞。

考虑 76pts 暴力分，把链提取出来。

可以发现 $K=2$ 的时候简单 $dp$ 一下就可以了，因为路径偏离这条链肯定是不优的。

$K=3$ 的时候就还需要记多一个"最后一步跳到距离节点 $i$ 距离为 $1$"的状态，因为这时候往旁边跳一步可能更优，参考样例 $3$。

然后可以写出一个 $5$ 维转移矩阵，据说别人都是三维的可以直接倍增，但好像我的垃圾做法会爆空间，而树剖会爆时间 QAQ。

所以打了点分治，离线搞搞就能过了。

好像点分治其实可以不用矩阵实现，但合并两条链挺麻烦的。