题解：P11259 [GDKOI2023 普及组] 海星
水星湖
·
·
题解
树形 dp。
一个点有三种状态：
我们发现一个点为边缘节点时，该点对应的中心节点可能是它的子节点之一也可能是它的父节点，所以要把这两种情况分开讨论。
对于每个点 u，设 f_{u,0} 表示该点不属于任何海星，f_{u,1} 表示该点为边缘节点，且该点对应的中心节点是它的儿子之一，f_{u,2} 表示该点是中心节点，且选择的边缘节点仅有该点的子节点，f_{u,3} 表示该点是中心节点，且选择的边缘节点中包含该点的父节点。没有设一个东西表示“该点为边缘节点，对应的中心节点是父节点”的原因是可以从确定该点父节点是中心节点之后，直接从该点不属于任何海星的状态转移。
考虑转移：
显然，f_{u,0}=\sum_{v\in son_u} \max(f_{v,0},f_{v,1},f_{v,2})，因为该点不属于任何海星，所以该点必然不是一个中心节点，故不可以从 f_{v,3} 转移。
根据状态定义可以看出，f_{u,1} 需要从 f_{v,3} 转移，因为每个点只能对应一个中心节点，所以我们必须从所有子节点中选择一个点 v 从 f_{v,3} 转移，其余子节点同上。实现时，可以先令 f_{u,1}=\sum_{v\in son_u} \max(f_{v,0},f_{v,1},f_{v,2})，最后加上 \max_{v\in son_u} (f_{v,3} - \max(f_{v,0},f_{v,1},f_{v,2})) 即可。
$f_{u,3}$ 与 $f_{u,2}$ 类似，只需要在 $f_{u,2}$ 的基础上额外考虑一下父节点的贡献即可。
```cpp
#include <bits/stdc++.h>
using namespace std;
namespace z {
#define int long long
const int N = 1e5 + 5, inf = 1e18;
vector<int> p[N];
int n, a[N], f[N][4];
void dfs(int u, int fa) {
int mx = -inf, val1 = a[u], val2 = -a[u];
vector<int> v1, v2;
for(int v : p[u]) {
if(v == fa) continue;
dfs(v, u);
int tmp = max({f[v][0], f[v][1], f[v][2]});
f[u][0] += tmp; f[u][1] += tmp;
mx = max(mx, f[v][3] - tmp);
v1.push_back(f[v][0] - tmp - a[v]);
v2.push_back(f[v][0] - tmp + a[v]);
}
sort(v1.begin(), v1.end(), greater<int>());
sort(v2.begin(), v2.end(), greater<int>());
if(p[u].size() > (bool)fa) {
val1 += f[u][0], val2 += f[u][0];
f[u][1] += mx;
val1 += v1[0], val2 += v2[0];
for(int i = 1; i < (int)v1.size(); i++)
if(v1[i] > 0) val1 += v1[i];
for(int i = 1; i < (int)v2.size(); i++)
if(v2[i] > 0) val2 += v2[i];
f[u][2] = max(val1, val2);
f[u][3] = max(val1 - a[fa], val2 + a[fa]);
} else f[u][3] = abs(a[fa] - a[u]);
}
void main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);cout.tie(nullptr);
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i < n; i++) {
int u, v; cin >> u >> v;
p[u].push_back(v);
p[v].push_back(u);
}
dfs(1, 0);
cout << max({f[1][0], f[1][1], f[1][2]}) << '\n';
}
#undef int
}
int main()
{
z::main();
return 0;
}
```