题目链接
题意
给定n个点的树，每个点有一个点权wi, 每次选一个点u，则树上u和距离u wi范围内的所有点都会被染色。
问：最少选几个点使得n个点都被染色。
思路：树形dp
对于某个点u
down[u][j] 表示u以及u向下深度为 j 的点没有被染色的最小花费。
up[u][j] 表示u以及u向上距离为j的点已经被染色的最小花费。
设u点的儿子们为v, v2, v3 ···，每个点点权为w[]数组
3种转移：
1、对于down[u][i] 显然就是子树的down数组求和，，特殊一点就是down[u][0](含义为u的子树中 除了u没有被染色，别的点都染色的最小花费，所以是sigma(up[v][0]) )
2、如果选u点，则显然答案为 1 + sigma(down[v][ w[u]-1 ]) ，更新给up[u][w[u]]
3、如果不选u点，则从某个儿子的up数组更新过来答案为 up[v][j] + (down[u][ j-1 ]-down[v][j-2])
最后保持up 和 down的单调性。
代码及强力的小数据
版权声明：本文为博主原创文章，未经博主允许不得转载。
幸运并非没有恐惧和烦恼;厄运并非没有安慰与希望。
