A simple Blog for wyx I've been down the bottle hoping.
BZOJ 2286 树形dp
发表于: | 分类: Oi | 评论:0 | 阅读:122

第一次写虚树……
学了一下午
我们先来看朴素的$dp$吧
用$f(i)$表示将$i$及其子树与1隔离的最小花费
如果$i$是一个资源点 $f(i) = inf$
否则的话 $f(i) = min {f{son_i},val}$
说白了就是让儿子做还是自己选边的问题……
裸$dp$谁都会,一次是$O(n)$的
m次 , $O(mn)$
$GG$

我们可以利用虚树
具体实现,按照 $DFS$ 序从小到大插入,每次插入时求一个当前点和栈顶的点的 $LCA$。
然后进行弹栈,从栈顶开始将所有深度大于 $LCA$ 的点弹出栈,进行一个特判,如果栈顶深度大于 $LCA$ 且栈中下一个元素深度小于 $LCA$,说明是在这两个点之间插入新的 $LCA$,要更改父亲关系。
最后将插入点的父亲设为这个 $LCA$,并把插入点压入栈。
有一些细节

我实在不想粘我的代码了 改的惨不忍睹……
想看的去找P妈的代码吧 $Orz PoPoqqq$
传送门

Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP