树形dp 小结

  • Post author:
  • Post category:其他


只能勉强称之为树形dp的傻逼问题:


[POJ1655]Balancing Act


树的重心,经典问题,但是非常简单啊。。。

用size维护一下就好辣!


[BZOJ2435][Noi2011]道路修建


Noi的题竟然有这么水。。。

树的?序遍历

树的遍历问题,大多数与根有关。也就是说,以?为根经常在dp的状态中出现。


[NOIP2003]加分二叉树

树的直径(最长链)相关(经典问题):

做法一:两遍dfs

首先从任何一个点出发找到一个离它最远的点,再从这个点出发找到离它最远的点。第二次dfs到的就是最长链。

但是这种方法不能搞负边权。于是就有了更优的做法——

做法二:树形dp

f(i)和g(i)分别表示以i为根节点的子树的到叶子节点的最远距离和次远距离。然后dp。


[tyvj1520]树的直径


裸题= =


[BZOJ1509][NOI2003]逃学的小孩


dp不知道好不好写,这种题直接上dfs叭?


[BZOJ2657][Zjoi2012]旅游(journey)


主要是你需要判断出来它是一个树,并且是一个最长链。


[BZOJ3124][Sdoi2013]直径


第一问就是简单的求直径,第二问的话需要一些性质来支撑。还是很好的一道题。


[BZOJ2282][Sdoi2011]消防


同样是关于树的直径的性质。


[BZOJ1912][Apio2010]patrol巡逻


这道题就是所谓的”负边权“问题,而且运用了一个非常巧妙的相互抵消的思想。

儿子转移到父亲——0/1状态转移(经典问题):

这种问题的状态经常是这样的f(i,0/1)表示以i为根,0/1分别代表一种的根的状态。比如说选或者不选,向上或者向下。当分类讨论情况非常多时,也有可能会出现0123这样表示状态的情况,代码就比较繁琐了。

没有上司的舞会


[BZOJ1097]树的路径覆盖


巧妙的状态表示!


[BZOJ2060][Usaco2010 Nov]Visiting Cows 拜访奶牛

父亲转移到儿子——少见,但是经典

为什么要用到父亲转移到儿子呢?因为有的时候需要维护一个“这个点不能走它子树里的点”然后balabala。这样的题通常不是很简单,因为要考虑到它父亲和它兄弟共同的影响。

有一些O(n^2)dp比较简单的题如果想要优化成O(n)的就要用到这种dp方法!

大多数都和树的直径一样,用到了次大值的思想吧。


[HDU2196]Computer


其实和树的直径有点相似,不过也不大一样。


[loli的测试题]宝藏


我认为这是我见过的较复杂的树形dp之一了。既有儿子向父亲转移又有父亲向儿子转移,并且运用了贪心和次大值的思想。

贪心可做?


[BZOJ1596][Usaco2008 Jan]电话网络


树上全覆盖问题:dp的话通常3个状态。

贪心水过。。。


[BZOJ2097][Usaco2010 Dec]Exercise 奶牛健美操


这个都不能叫做dp啊,就是个贪心其实。

但是和最长链相关哦


[BZOJ1907]树的路径覆盖


这个确实贪心可做,并且我认为贪心的思路感受一下是对的。。

不过我感觉这个树形dp要更有价值,因为拐点和不是拐点这个状态表示的非常巧妙。

树形dp+维护(父子关系!)

从一个树上的父节点移动到儿子节点只有一条边的变动,那么我们能不能动态维护一些信息呢?

题目往往是要求你找出一个点来满足一个什么条件,往往先求出来以1为根的再转移。


[BZOJ1827][Usaco2010 Mar]gather 奶牛大集会



[BZOJ1131][POI2008]Sta

树上背包:掌握最弱没有之一

我都不大敢写这个分类,因为没有搞懂的地方太多了。。


[CODEVS1378]选课


我不会做啊,是学姐帮我写了代码= =我才勉强理解

背包和树形dp一结合就是goushi


[BZOJ4033][HAOI2015]T1


思路:考虑每一条边的贡献。

这种思路在树的题里非常常见,一定要注意。


[POJ1155]TELE

环套树:拆环或讨论环

拆环的思路:

找出来环了之后随便砍一条边,那么你在这棵树上搞事情的时候就必须手动控制原先有边的两个点。

讨论环的思路:

找出来环了之后再外向树上分别dp,然后再将环上的点组合起来。


[BZOJ1040][ZJOI2008]骑士


这道题拆环或者讨论环都是可以的诶,两种思路。感觉这是一道挺好的题。


[BZOJ3242][Noi2013]快餐店


Noi的题,非常有价值。思维和码力++

多叉树转二叉树:到底有没有用?

基本上没有用过这种dp的方法,因为学姐说没有用???也没有碰见过什么题,但是据说某些题只有这样才好搞?


[BZOJ1812][Ioi2005]riv


先链到题目去叭。。本王写了但是由于不是很了解多叉转二叉就没写题解。。

树形dp有的时候只是一个辅助的工具!

用dp算出来一个值之后再用这个值搞其他的事情大有题在。。。


[BZOJ1060][ZJOI2007]时态同步



版权声明:本文为Clove_unique原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。