只能勉强称之为树形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]时态同步