【BZOJ2286】【SDOI2011】消耗战

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

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

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

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

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

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

这题的dp还是比较简单的

说点什么

1 评论 在 "【BZOJ2286】【SDOI2011】消耗战"

提醒
排序:   最新 | 最旧 | 得票最多
成员

泥天天刷火题!

wpDiscuz