比赛经历

比赛之前家长跟我说，CSP 对我来说难度不高，可以尝试着把所有题都先看一遍再写。我看过去年 CSP-S 一些高水平选手的游记，很多也是先把所有题都看一遍，甚至直接想出 T1~T3 的做法，再开始写代码。

在开考之前我也有过这个想法，但是当我用 5min 的时间粗略的扫了一眼四个题之后，觉得还是不能先把所有题想一遍再开始写，原因有三：

一是平时模拟赛我都是看一题写一题，没有这样搞过，在正赛临时改变策略不是一个明智的选择，心里没底；

二是这样做风险很大，如果三个题中有题目想了假做法，对心态会有很大的影响。尤其是假如此时剩下的时间没有很多，来不及重新思考，重新编写代码，那么麻烦就大了，我几乎不可能顶着时间不足和心态爆炸把这个题做出来。

三是之前我和 zdc 聊过，OI 选手最怕的就是多线作战。一题一题的做，肯定比同时做两三个题要更好。

于是我最终还是选择一题一题顺序开题，平推过去。

先看 T1，很快转成了形式化的题意，做 polylog 复杂度是简单的，但是线性感觉比较困难。重新阅读了一遍题面，发现自己看错题了，看对之后只需要简单双指针即可，开场 10min 左右通过了 T1。

接着开 T2，题面写得比较复杂，我边看边把简化后的题意写在纸上，最后看纸上的题意发现直接写个 floyd 就做完了。这个题是纯粹的阅读理解，开场 30min 左右通过了 T2。

再开 T3，看完题面之后我就意识到了这个题必然不“规整”，具体的说不是写几个板子拼一起就能过的，而必然需要考虑清楚细节，可能还要花一些时间调试代码才能通过。于是在想题之初我就做好了打持久战的准备。

于是我对着 T3 一遍一遍画图，推导出一条一条结论和性质，最后大概知道怎么做了。但是此时我没有急着开始写，而是再把整个过程重新想了一遍，确认无误之后再开始写代码。

代码比想象中好写得多，对着样例简单调了调就通过了所有大样例。不过这个题感觉上就很容易挂，于是我上了个拍，确认没问题之后再开的 T4，此时开场 90min。

和一些选手交流的时候，他们通过前三题的时间普遍在 2h 左右。我之所以能这么快通过了 T3，很大程度上就是因为我把整个题想清楚之后再开始写，省下了很多调试的时间，开 T4 时的精神也更好。

去洗了把脸，冷静了一下，开 T4，发现大概是一道推性质 DS 题，感觉优势在我，于是直接开始思考正解。

直径很容易让人想到树上圆理论，毕竟这是 APIO2026 才考过的算法。但是稍微思考之后，我排除了这个方向，而是转为我认为更对的方向：钦定一个点在连通块中，再考虑另一个连通块的位置。

先考虑只有一个连通块的情况，一个简单的做法是以树的中点为根，二分之后直接贪。这是因为连通块如果不包含树的中心，答案直接就是 \(len\over 2\)，\(len\) 是直径长度。而如果包含了中心，答案上界就是这个，因此必然包含中心。

但是两个连通块并没有这么优良的性质，我们不能直接认为某个特殊的点为根（否则就要枚举所有点为根的情况），因此我尝试思考如何在不钦定根的前提下做连通块数为一的问题。简单思考之后我发现这也是简单的，只需要枚举连通块中在原树上深度最浅的点 \(x\)，那么 \(x\) 子树外被我们钦定不存在 \(S\) 中的点，只需要限制子树外所有点到 \(x\) 的距离 \(\le mid\)，然后在子树内贪就好了。

这个时候，我想当然的把做法尝试往两个连通块的情况推广——枚举第二个连通块的根是 \(x\) 子树中的 \(y\)，然后再来计算答案。

根据这个做法，我接着往下推导出了许多性质，最后得到了一个非常简洁的做法。推导性质的时候，因为时间充裕，每条性质我都进行了多次验证，确认无误再往下想。

此时大概是开场 2h30min，我觉得已经可以直接开写了。保险起见，我打算先写基于这个做法的 \(O(n^2\log n)\) 暴力，再把 \(n^2\) 部分优化成线性就好。

写完并调试通过小样例，此时大概是开场 3h，我测了第三个大样例，发现最后一组数据答案是 9，我的输出是 10！起初我不以为然，觉得做法既然是对的，只需要简单调试一下就好。可随着时间流逝，我始终看不出我的做法哪里错了。

17:45 左右，也就是还有 40min 的时候，我整个人陷入了极度紧张的状态，浑身发热，脑子里一片糨糊。CSP-S 2024 的失败历历在目，当时的我也是 90min 通过前三个题，盲目冲击 T4，最后获得 0pts。那年 WC 线是 316，我获得正好 300 分，去不了 WC。事后来看，T4 的 40pts 对于当时的我来说是简单的，70+pts 是本质不难，当时的我理应想到的。正是因为有过这样的经历，所以在这个时刻我才格外紧张，我很害怕这样的惨案重演。

17:48 的时候，我意识到麻烦大了。我强制让自己冷静下来，在接下来的两分钟内，我重新审视了自己的做法，很快就发现了问题——整个做法的第一步，枚举第二个连通块的根是 \(x\) 子树中的 \(y\)，完全是错误的！

\(x,y\) 并不一定在原树上有祖先关系！

“只需要枚举连通块中在原树上深度最浅的点 \(x\)，那么 \(x\) 子树外被我们钦定不存在 \(S\) 中的点”这句推导是建立在没有第二个连通块的情况下的，当存在第二个连通块时，\(x\) 子树外当然可以有 \(S\) 中的点。

因为少考虑了情况，我的答案确实有可能比大样例大。

时间所剩无几，我知道自己调不出来了。同时我测了第四个大样例，出人意料的是 \(O(n^2\log n)\) 很快的跑出了 \(\sum n\le 10^5\) 的数据。但是当我看具体输出时，发现答案全都比正确答案小很多。

此时有两种可能，我的数组开小了，或者我还有别的地方写挂了，但是无论是哪种可能，我都明白自己已经不可能通过这个题，因为做法根本上就是错的。

于是我转而思考如何在剩余的半个小时内让分数最大化，根据一些性质，我发现有一个非常好写的做法：考虑两个连通块最近的点 \(x,y\)，其之间的路径，以及路径上挂着的其他子树上必然不存在 \(S\) 中的点。于是二分答案之后唯一的限制就是 \(x,y\) 路径以及路径上挂着的子树，所有点都能被 \(x,y\) 在不超过 \(mid\) 的距离内覆盖到。而此时，整棵树可以被划分成 \(x,y\) 两个完全独立的部分，这个直接贪就好！

直接模拟这个过程是 \(O(n^3\log n)\) 的，但是如果我们枚举 \(x\) 之后，\(y\) 需要考虑的部分必然是一个子树，我们只需要求出一个子树的答案就好，这个是简单的，于是就可以直接拿下 \(O(n^2\log n)\)，3s 的时限感觉跑过 \(n\le 4000,\sum n\le 10000\) 是没有问题的，那么这个题我至少就有 50pts 了。

此时已经 18:00，我当机立断，把代码改成了 \(O(n^2\log n)\)，18:10 的时候我初步写完，但是小样例全错。这个时候我反而没有害怕，因为这个做法的我想得非常清楚，我知道每个部分应该怎么写，于是只要简单调试就能通过。

18:20，我调过了所有小样例，并通过了大样例 3。大样例 4 完全跑不出来，我其实觉得有一定概率挂，但是想着最后 10min，就算上了拍，拍挂了，也改不出来了。于是再三检查文件名和文件夹名，直到下考。

出了考场，我觉得这场发挥极其招笑，前面 90min 拿下 300pts，后面 30min 拿下 50pts，中间的 2h 都是无效思考。而且我不觉得 T4 50pts 是困难的，就算有些选手前三题花了较长时间，他们也能很快写出 T4 50pts，如果再拼两个特殊性质，可以获得 70pts 的高分，反而比我高了。

于是走在楼梯间的时候我心情不太好，甚至有点担心能不能去得了 WC。有很多人来问我分数，我都敷衍过去了，因为我觉得实在是有点拿不出手。

在学校门口碰到了一中的 szy 和 yjf，他们都跟我说自己只有 340pts，这个时候我觉得不太对劲了，我打得招笑可能是发挥不好，但是他们分数也不高，那这个 T4 看来是有难度的啊？也许 350pts 也是一个不低的分数？随后看了眼 u 群，发现竟然没有几个人声称自己通过了 T4，原来这个题很困难？

不过我自己也知道，题目难不难，和我的发挥好不好其实是两回事。就算这个 T4 很难，我也应该是从容的写出 \(O(n^2\log n)\) 然后拼两个暴力，而不是让一场 CSP 把自己弄得如此狼狈。

随后在联考群，我看到很多选手声称自己在 [300,320] 之间，当然也有和我料想得一样，写个 \(O(n^2\log n)\) 拼两个特殊性质拿到 370pts 的选手。

在回家的路上，我终于接受了事实——我的最后一场 CSP，就这么结束了。