1. 题目链接
Kickstart Round F 2019 C. Spectating Villages
2. 题目描述
有 $V$ $(2\le N\le 10^5)$ 个村庄，他们由 $V-1$ 条无向边直接或间接相连，无重边，无自环。每个村庄有一个漂亮值(即点权)，编号为 $i$ 的村庄的漂亮值为 $B_i$ $(-10^5\le B_i \le 10^5)$。
你可以选择在一些村庄安装电灯，如果你在一个村庄安装了电灯，那么这个村庄以及与这个村庄直接相连的所有村庄也将被点亮。
现在你可以在一些村庄上安装电灯（也可以都不安装），求被点亮的村庄的漂亮值之和的最大值。
3. 解题思路
图是一个棵无根树。可以选择某一个顶点作为根节点进行树形DP。
状态定义为 ：
- $dp[u][0]$ 表示村庄 $u$ 为根节点的子树中，在村庄 $u$ 没有安装电灯，同时村庄 $u$ 不被点亮的条件下的最大漂亮值之和。
- $dp[u][1]$ 表示村庄 $u$ 为根节点的子树中，在村庄 $u$ 安装了电灯的条件下的最大漂亮值之和。
- $dp[u][2]$ 表示村庄 $u$ 为根节点的子树中，在村庄 $u$ 没有安装电灯，同时村庄 $u$ 被点亮的条件下的最大漂亮值之和。
对于村庄 $u$ 为根节点的子树中，有：
- 当村庄 $u$ 没有安装电灯，同时村庄 $u$ 不被点亮：其子节点一定不能安装电灯。
- 当村庄 $u$ 安装了电灯：其子节点可以随意。
- 当村庄 $u$ 没有安装电灯，同时村庄 $u$ 被点亮：他的子节点中至少有一个安装了电灯。我们这里可以选$\arg\max_\limits{v \in son(u)}\lbrace dp[v][1]-\max\lbrace dp[u][0],dp[u][1]\rbrace\rbrace$ 被点亮，其他子节点可以随意。
具体的转移方程可以见代码。
