OK…我无论怎么搞都是TLE。。。这道题我是按离线和启发式合并的思想来做的。。
就是说在dfs的时候对每个点维护一个treap表示其中所有点的权值。。然后dfs的时候启发式合并。。就是把小的拆开加到大的里面去。。然后直接select就可以了。。
我用了Treap和启发式暴力拆合并的思想来搞这道题。。无论如何都悲剧。。
我都快疯了。。我一开始是用暴力指针的treap的。。后来自己写了个回收管理器。。没用。。又改用数组了。。照样TLE。。然后我又把树的结构有vector改成用数组的链表。。TLE。。然后我优化输入输出。。TLE。。。然后我改成前向星。。TLE。。然后我想到随机数可能很慢。。于是直接用随机打乱的1-n排列来作为key的值。。TLE。。
….然后我感觉treap不是随机的嘛。。就狂交拼RP。。交了N次。。快疯了。。然后有神牛告诉我插入和选K大改成的非递归的。。TLE。。然后他告诉我用SBT。。然后我直接撞墙了。。
还能有什么优化啊。。就不能用treap AC这道题么。。。
我去写写SBT了。。上次我写了个比treap还慢。。真想撞死。。
我好菜啊。。
整天被题虐的。。一个下午搞的我内分泌都快失调了。。
这个题果然bt……我写了平衡树加启发合并，TLE……用线段树logN回答第k大，也TLE……
回复oimaster：这个MS只能用动态树做了囧。。
回复WJBZBMR：没用……第k大这个比较难解……
瞎搞了半天AC了，把平衡树改成排序二叉树……
回复oimaster：饿。。不是这样的。。就是说从小到大一个个添加节点的权值，然后用动态树维护每个节点中还需要插入多少个点就可以输出，然后维护每条路径上的最小值，如果是0的话就输出结果，然后搞一下就OK了。。
回复WJBZBMR：这……您写过吗……
回复oimaster：额。。我DT写的贼慢。。严重TLE囧。。
我也在搞这道题目，死都是TLE
回复sad_sadness：额。可以用NLogN的区间K小算法搞掉。。完全忽视它是一棵树。。。
NlogN的怎么搞？