自动搬运

查看原文

来自洛谷，原作者为

	水星湖 菜

搬运于2025-08-24 23:05:48，当前版本为作者最后更新于2024-11-24 11:11:50，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

树形 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,2}$ 转移同样可以使用 $f_{u,1}$ 转移时的方式，即先令 $f_{u,2}=\sum_{v\in son_u} \max(f_{v,0},f_{v,1},f_{v,2})$，然后将一部分 $\max(f_{v,0},f_{v,1},f_{v,2})$ 替换为 $f_{v,0} + val_v$，$val_v$ 为 $v$ （边缘节点）的贡献，因为带绝对值，所以贡献要分正负计算。注意到，如果将一个点 $v$ 的 $\max(f_{v,0},f_{v,1},f_{v,2})$ 替换为 $f_{v,0} + val_v$，相当于 $f_{u,2} \gets f_{u,2}+(f_{v,0} + val_v-\max(f_{v,0},f_{v,1},f_{v,2}))$，所以实现时可以单独存 $f_{v,0}+val_v-\max(f_{v,0},f_{v,1},f_{v,2})$，只将其中 $>0$ 的计入贡献即可，但是注意如果没有 $>0$ 的值时，由于海星至少两个点，所以也必须选一个计入贡献（显然选最大的）。

$f_{u,3}$ 与 $f_{u,2}$ 类似，只需要在 $f_{u,2}$ 的基础上额外考虑一下父节点的贡献即可。

#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;
}