P4845 LJJ 爱数树

Eden 偶然间拿到了一张藏宝图，值得一提的是，这是张无向联通图，有 $n$ 个节点，$n-1$ 条长度为 $1$ 的边，即一颗树。每个节点上都标有该地点的宝藏数量 $w_i$。 然而宝藏太多，不能一次性搬完，Eden 花费其所有积蓄买来 $k$ 个摄像头，每个摄像头能观测的距离范围是 $r$（我们规定树上任意两点距离为其最短路径的长度）。为了确保宝藏尽可能不被他人拿走，Eden 将要在这棵树上的至多 $k$ 个节点处布置摄像头（于是与该节点距离 $\le r$ 的节点都能被观测到）。 Eden 想要使能被观测到的节点的宝藏数量（即 $w_i$）之和最大化，于是他把这个问题交给了爱数树的 LJJ。让 LJJ 枚举所有可能放置摄像头的情况，来筛选出最优的方案。 LJJ 数到一半，发现这个方案数量太多了，于是他把问题抛给了你， 请你输出能被观测到的节点的 $w_i$ 之和的最大值。

无

无

对于 $10\%$ 的数据，保证 $n\le20$，$r\le 20$，$w_i\le20$； 对于 $40\%$ 的数据，保证 $n\le50$，$r\le 50$，$w_i\le50$； 对于另外 $20\%$ 的数据，保证 $k\le2$； 对于另外 $10\%$ 的数据，保证给出的树是一条链。 对于 $100\%$ 的数据，保证 $1\le k \le n\le10^3$，$1\le r\le 10^3$，$1\le w_i\le10^6$，$1\le T\le 5$，$1\le x,y\le n$。 官方题解请查看 [https://www.cnblogs.com/Blog-of-Eden/p/9367521.html](https://www.cnblogs.com/Blog-of-Eden/p/9367521.html)。