今天是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，发现输出的顺序是乱的，才发现忘了离线询问顺序输出答案。加了个存答案的数组就搞定了。
感觉应该差不多了。交一发。
然后。
鄂公网安备 42010202000505 号