【BZOJ2286】【SDOI2011】消耗战

我好像并没有写过虚树的题

然而我™为什么出过一道虚树题啊

那么作为虚树第一题还是讲一下虚树吧

虚树就是把所有的询问结点和他们两两的LCA取出新建一棵树,边权替换后再在上面进行dp等操作

具体实现可以将所有点按照dfs序排序,相邻的求LCA并加入,再去重,一定可以满足条件

连边的话就再按dfs序排序,建一个栈,每次不断将栈顶不为当前点的父辈的点弹出,直到是父辈节点,从栈顶向这个点连一条边,再将这个点丢进栈里即可

这题的dp还是比较简单的

1
说点什么

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

泥天天刷火题!