HDU5242

树上贪心

---

---

HDU 5242

题意

给一棵点权树以及树的相对父子，问从根出发选择 $k$ 条路径的最大点权和，每个点的权值只能算一次。
$(n,k \le 10^5)$

题解

• 由于已经给出了相对父子关系，从叶子结点向上到根的路径是唯一。
• dp记录每个点向上权值和。
• 对dp权值和排序，从大到小求出每个点向上可以得到的点权和，并把点更新访问过。
• 这样每次每个点实际是找到最近被访问过的点。
• 取前 $k$ 个最大即可。