题目内容

游游有一个 $n$ 个点 $n-1$ 条边的无向树，其中 $1$ 号点为根节点，但其点权中可能存在负数。

现在如果树非空，则游游可以对树进行一些“删点”操作任意次(两种都是任意次)，具体的：

●游游可以选择任意一个度数恰好为 $1$ 的非根节点，从树中直接删除该点和连接该点的边。

●游游可以选择任意一个度数恰好为 $2$ 的非根节点，从树中删除该点，并将该点连接的两个邻点连接起来。

思路与方法

本题给定一棵以 1 号节点为根的无向树，每个节点有一个权值（可为负）。允许对任意非根节点进行两种删除操作：

1. 删除度为 1 的非根叶子节点。
2. 删除度为 2 的非根中间节点，并将其两个邻居直接连接。

操作任意次后，希望最大化剩余节点权值之和，且根节点 1 必须保留。

树上 DP 模型