HDU5242

树上贪心



HDU 5242

题意

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

题解

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