【BZOJ1095】【ZJOI2007】捉迷藏

LCF太不良心辣居然放QTREE4出来让我码了2h+还没码出来

然后当日考试GG

先把这个不带边权的做了吧 这个好做一些。。

括号序列那种神方法还不会。。

我写的是传说中的动态树分治:将点分的结构存下来形成一个新的树形结构,深度是\(log\)级别的,那么每个点就只会在\(log\)个点的子树中出现

每个点维护两个堆分别维护:

  • 它所在子树内距离它父亲的距离(点分形成的结构)
  • 它每个分支到它的最远距离

再一个全局堆维护答案

1
说点什么

1 Comment threads
0 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
1 Comment authors
Recent comment authors
  Subscribe  
最新 最旧 得票最多
提醒
成员
LCF

其实我当时放qtree4出来就没期望有人写出来……
毕竟我写了很久……
所以只能选择%%%考场上AC此题的lun大爷