题目内容

给定一棵有根树，节点编号为 $1$ ~ $n$ ，其中节点 $1$ 为根节点。

每个节点都有一个整数收益 $r_i$ 。

此外，每个节点还附带一个中和成本 $c_i$ ，表示你可以花费 $c_i$ 的代价将该节点的收益置为 $0$ (即忽略该节点原有的收益)。

你还可以花费一定代价对树上的边进行切断操作。对任一边，你可以支付该边的切断代价，从而切断这条边，切断后，与根节点不再连通的部分将被移除。

题解

题目描述

给定一棵根为节点1的树，每个节点有权值$r_i$和中和成本$c_i$。可以选择切断边（支付代价$d$）或中和节点（支付$c_i$使收益为0）。求根所在连通块的最大净收益（总收益减去操作代价）。

思路分析

树形动态规划：后序遍历每个节点，计算在保留该节点时，中和或不中和的最大贡献，并处理子节点的切断或保留决策。