树形DP

题目链接 题意：将一棵树的若干点染成黑色，要求满足对于任何一个点u，至少存在一个距离其k以内的点v被染成黑色，问染色方案数。

题目链接 题意：一个舞会，每个人有一个val，给出n个人之间的领导和被领导关系，一个人不愿意与他的领导同时参加，问一种安排方案，使得参加的人的val和最大，问这个最大的和是多少。

资料１

cf682C题目链接 题意：给一棵树。。有点权和边权。。。如果一个点v的子树中存在某点u，满足dis(u,v)>a[u]，那么点v就非常sad…

hdu 2196 题意：给出一棵树，求距离每个点的最远距离是多少。 思路：最远距离什么的，能想到树的直径，但是有什么关系呢？我们在求树的直径的时候，直径的两个端点是可以知道的。如果再从两个端点分别做两次 bfs，每个点取两个距离的较大值就是答案。。？

题目链接 题意：n个人的上下级关系形成一棵树..每一个人有一个val（可正可负），要选若干个人参加一个party，要求是一个人和他的直接上级不能同时在场。问参加party的人最大的val之和。

树，一种十分优美的数据结构，因为它本身就具有的递归性，所以它和子树间能相互传递很多信息，还因为它作为被限制的图在上面可进行的操作更多，所以各种用于不同地方的树都出现了，二叉树、三叉树、静态搜索树、AVL树，线段树、SPLAY树，后缀树等等.. 枚举那么多种数据结构只是想说树方面的内容相当多，本专辑只针对在树上的动态规划，即树形DP.做树形DP一般步骤是先将树转换为有根树，然后在树上进行深搜操作，从子节点或子树中返回信息层层往上更新至根节点。这里面的关键就是返回的信息部分，这个也没一般性的东西可讲，因为每道题目要求做的事都不尽相同。