解题思路

水源（根）必须保留。两类删点操作的效果是：对每个非根节点，可以选择保留它（从而保留它子树里各自独立的最优结构），也可以删掉它（此时它的子树只能留下至多一条“接到父亲”的最优链）。

对节点 $v$ 定义：

题目内容

园区供水管网是一棵 $n$ 个节点、 $n-1$ 条边的无向树，1 号节点为水源（根），第 $i$ 个节点有收益 $a_i$ （可能为负）。运维规程允许在管网非空时反复修剪，以便去掉亏损支路、保留高收益骨干。只要树非空，就可以反复执行下面两类删点操作（每种都可以任意次）：

水源必须保留。请计算操作结束后，剩余节点收益之和的最大值。