今天是Goodbye Bingshen。

好久没打UOJ比赛了，于是就来打了一次。

一开场看到第1题，感觉我以前思考过这个问题，于是推了个很简单的结论：如果 $n < 4$，答案是 $1$，否则是 $-1$。交上去以后重新想了下发现证明有问题，但重新证明以后发现结论是对的。

接着看第2题，构造题，继续猜结论，每个点和 $n$ 连边，自己试到 $n \le 9$ 好像都没有反例。也就这么交了。

交完以后重新想了下，发现如果 $n$ 大一点，答案是 $2n-3$，如果先构一条 $5$ 点的链，在中点往下构一个这种树，答案是 $3n-13$。卧槽。

于是就想枚举一下树的深度，然后先构最长链，再递归下去构造。用一个类似记忆化搜索的东西求了下发现最优解深度不超过 $70$，于是就 $10000\times 70^2$ 做完了。

看了下第三题，感觉暴力做法就是对于每个询问 $(s,t)$ 将 $s$ 子树的每个点对应一个平面点 $(w_i,d_i)$（$d_i$ 为 $i$ 在树中的深度）然后记 $f(x)=\min\{d_i|w_i\ge x\}$，$s$ 到 $t$ 的最大点权为 $w_\max$，答案就是 $\sum_{x=1}^{w_\max}f(x)+d_t-d_s$。这个好像可以维护一下单调栈之类的东西，然后算一下面积？不过这只是单次询问的。多次询问就把这个东西启发式合并一下……？

Splay启发式合并，应该是 $O(n\log^2n)$ 的？（反正我只会证明是 $O(n\log^2n)$）时限 $2\texttt{s}$？看起来可以过，写一写。

（UPD：后来immortalCO告诉我复杂度其实是 $O(n\log n)$）

于是就开始码Splay……码了一会儿有点虚犹豫要不要码下去，于是看了后两题。

第4题好神啊，似乎不太可做，先不管了。第5题……居然是个交互式证明，要理解源代码，看了下源代码巨长无比，不太容易理解，也先不管了。

后两题都不太可A，好像还是搞第3题比较有救？

于是继续码Splay。写完基本操作以后开始维护每个点到上一个点的类似面积的东西。代码写得很长，而且自己看着都觉得常数大有点要TLE的样子。

子任务制啊，要是挂了岂不是只有暴力分了？惨！

不过既然已经写了那我就把它写完吧。写完维护面积和、树上二分、插入节点以及删除左侧不在单调栈上的节点，最后写完查询，代码已经差不多4KB了。

然后，测一下样例1，RE了……实现逻辑出了不少问题，改了一会儿输出了6……原来我忘了加上 $d_t-d_s$ 了。加上以后过了样例1，再测样例2，发现输出的顺序是乱的，才发现忘了离线询问顺序输出答案。加了个存答案的数组就搞定了。

感觉应该差不多了。交一发。

然后。

喜闻乐见地WA成了 2 / 4。

也就是说我的后两个样例都没过。

比赛只剩不到90min，我还是把它调出来吧。由于我没写暴力，没法拍，于是大点WA了并没有什么好的办法。慢慢看代码吧。

仔细看了一遍没有发现任何可能导致错误的地方。那为啥能WA？发现我的输出答案有一个地方是 if(cond_A) ans = res_A; else ans = res_B;，然后试着把 res_B 换成 2333，结果后两个样例除了 2333 以外全对了。

疑似 res_B 的式子是错的，研究了半天发现并没有错。输出了树的形态，看上去也正常。这就很纳闷了。

只剩不到60min了。觉得还是把后两题暴力写一下吧。

写掉后两题各20分，剩下30min。无比紧张。看每一部分代码都觉得可能有问题但都没看出问题。最后想，既然式子是对的，并且只有那一种情况错了，那么导致这种情况的原因是什么呢？接着就意识到问题出在哪里了——

我有一步查询左边的和的时候忘记 splay() 到根了！

于是加了一行，去掉调试语句，测试，通过。这时候离结束只有20min了。花了3h多搞一题。感觉考场上我根本不敢干这么冒险的事情。

考完以后，matthew99告诉我，我写挂了。

完了，我的3h，我的3h就这么浪费了。写了这么久的题，挂了。完了，后两题我都只有20分，这样的话我分数一定会很低。

哎，难得打一次UOJ比赛居然挂成这样。算了还是把UOJ关了去想别的题吧。过一会儿再来看掉多少rating。

后来immortalCO说我第3题A了。哦？到UOJ一看，还真的A了。

十分感动。看来matthew99的消息并不靠谱啊

不过Splay的一个小错误能调那么久我的代码能力去哪了？毕竟我现在还是RP选手，代码能力不足，能调出来已经算是RP很好了。