题目链接 题意：将一棵树的若干点染成黑色，要求满足对于任何一个点u,至少存在一个距离其k以内的点v被染成黑色，问染色方案数。 思路：还没完全搞懂。。。记录一些idea... 参考题解 以及：该题解中说的children指的是子树全体。。。坑死好吗。。。坑了一晚上。。气啊。 **定义状态f[i][j]:以i为根的子树中，能向上贡献j个单位/需要外界往内填补j个单位，方案数** 如果是贡献，j为负数 转移的话，考虑不断合并子树,假如说当前处理x为根的子树 不妨把它的儿子按照输入顺序从左往右编号1~N **一开始到x的时候，初始状态f[x][-k] = f[x][1] = 1 ** 然后不断把儿子的信息合并给x 做法是x …

题目链接 题意：一个舞会，每个人有一个val，给出n个人之间的领导和被领导关系，一个人不愿意与他的领导同时参加，问一种安排方案，使得参加的人的val和最大，问这个最大的和是多少。 思路：树形dp模板题。 dp1[v]表示包含v节点的子树的最大值。 dp2[v]表示，不包含v节点的子树的最大值。 下面讲得很清楚。。 Now, similar to array problem, we have to make a decision about including node _V_ in our subset or not. If we include node _V_, we can't include any of its …

资料１

cf682C题目链接 题意：给一棵树。。有点权和边权。。。如果一个点v的子树中存在某点u,满足dis(u,v)>a[u]，那么点v就非常sad... dis(u,v)表示点u到v的距离。。。a[u]是u的点权。。现在问最少要删除多少个叶子节点才能使得没有点节点感到sad.. 思路：dfs一下。。。需要注意的是边权有负数。。。所以类似于区间的最大连续区间和。。。我们也也可以维护在树上的最大连续和。。。只需要如果当前为负就变成0即可。。。 /* *********************************************** Author :111qqz Created Time :2016年07月18 …

hdu2196 题意：给出一棵树。。。求距离每个点的最远距离是多少。。。 思路：最远距离什么的。。能想到树的直径。。。但是有什么关系呢？ 我们在求树的直径的时候。。。直径的两个端点是可以知道的。。。如果再从两个端点分别做两次bfs。。。每个点取两个距离的较大值就是答案。。。。？ 1A. /* *********************************************** Author :111qqz Created Time :2016年07月12日 星期二 13时29分49秒 File Name :code/hdu/2196.cpp …

题目链接 题意：n个人的上下级关系形成一棵树..每一个人有一个val（可正可负），要选若干个人参加一个party,要求是一个人和他的直接上级不能同时在场。问参加party的人最大的val之和。 思路：树形dp入门题。 dp[i][0]和dp[i][1]分别表示第i个人不参加和参加party对应的val和。 注意dp转移方程是放在每次dfs之后的回溯位置的。。。 这样做的话访问是从根节点到叶子节点，更新就成了从叶子节点到根节点。。。 联想到数字三角形...其实是一样的。。 sad...dp苦手如我也开始刷dp了吗。。。。 /* *********************************************** Author …