又被抓摆了/kk

T4（T3？）Cactus to Tree

link

Solution

tmd，连tm \(\Theta(n^2)\) 都没有看出来！！！！！！/fn

考虑 \(\Theta(n^2)\) 怎么做，其实就是对于每一个点直接 BFS（似乎对正解也没有什么启发性？听简单的，但是似乎大家都没有写）。再考虑树怎么做，你发现就是对于一个点求最远距离。

然后放在这个图上面，可以发现的其实就是如干个环通过边连在一起。那我们可以发现的是，对于环上一个点求的时候，肯定是断开距它环的一半的那条边，然后就是求每个环到环的最小最大距离，这个直接建个圆方树换根dp一下就好了，断边方法也是跟上面一样的。

似乎可以做到 \(\Theta(n)\) 不过 \(\Theta(n\log n)\) 挺好做的，所以就补的 \(\Theta(n\log n)\)。

T2（T4？）[Ynoi2005] vti

link

Solution

Ynoi滚出模拟赛！！！！！/fn

纯口胡，不保证正确。我们一眼看出不会低于 \(\Theta(n\sqrt n)\)，因为链的时候就是区间正序对数了，所以我们也就明白这个题目需要二次离线了（开摆