题目描述

难度分:$2000$

输入$T(\leq 10^4)$表示$T$组数据。所有数据的$n$之和$\leq 2 \times 10^5$。

每组数据输入$n(1 \leq n \leq 2 \times 10^5)$，$c(1 \leq c \leq 10^9)$和长为$n$的数组$a(-10^9 \leq a[i] \leq 10^9)$。

然后输入一棵无向树的$n-1$条边，节点编号从$1$到$n$。节点$v$的点权为$a[v]$。

你可以标记树上的一些点。每当你标记一个点$v$，就把$v$的所有邻居的点权都减少$c$。注意一个节点的点权可以被多次减少。

输出你标记的节点的点权的最大和。比如$n=2$，如果两个节点都标记，那么互相把对方的点权减$c$，答案为$a[1]+a[2]-c \times 2$。

输入样例

5
3 1
2 3 1
1 2
2 3
3 1
3 6 3
1 2
2 3
3 1
-2 -3 -1
1 2
2 3
6 1
5 -4 3 6 7 3
4 1
5 1
3 5
3 6
1 2
8 1
3 5 2 7 8 5 -3 -4
7 3
1 8
4 3
3 5
7 6
8 7
2 1

输出样例

3
8
0
17
26

算法

树形DP

比较容易想到是树形DP的做法，以节点$1$为整棵树的根节点，直接从$1$开始递归。

状态定义

$f[u][0]$和$f[u][1]$分别表示在不标记和标记$u$节点的情况下，以$u$为根的子树可以得到的标记节点最大点权和。在这个定义下，最终的答案就是$max(f[1][0],f[1][1])$。

状态转移

如果不标记$u$，初始化$f[u][0]=0$，接下来遍历$u$的子节点$v$，此时$v$是否标记都不会影响到$f[u][0]$，因为$u$节点是不标记的，不会增加任何的点权值，状态转移方程为$f[u][0]=\Sigma_{v}max(f[v][0],f[v][1])$。

如果标记$u$，初始化$f[u][1]=a[u]$，同样还是遍历$u$的子节点$v$。如果$v$不标记，也不会影响$f[u][1]$；如果$v$标记，那么$a[v]$和$a[u]$就都会减少$c$，所以状态转移方程为$f[u][1]=\Sigma_{v}max(f[v][0],f[v][1]-2 \times c)$。

复杂度分析

时间复杂度

对整棵树进行一次DFS就能求得答案，因此算法的时间复杂度为$O(n)$。

空间复杂度

除了树的邻接表，以及点权数组$a$，静态的空间消耗就是DP矩阵$f$。但在算法的过程中，对整棵树进行递归在最差情况下树退化成链，递归深度可以达到$O(n)$，这是动态的空间消耗。因此，整个算法的额外空间复杂度为$O(n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

const int N = 200010;
int t, n, c, a[N];
LL f[N][2];
vector<int> graph[N];

void dfs(int u, int fa) {
    f[u][0] = 0;        // 不标记u
    f[u][1] = a[u];     // 标记u
    for(int v: graph[u]) {
        if(v == fa) continue;
        dfs(v, u);
        f[u][0] += max(f[v][0], f[v][1]);
        f[u][1] += max(f[v][0], f[v][1] - 2*c);
    }
}

int main() {
    scanf("%d", &t);
    while(t--) {
        scanf("%d%d", &n, &c);
        for(int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
            f[i][0] = f[i][1] = -1e18;
            graph[i].clear();
        }
        for(int i = 1; i < n; i++) {
            int u, v;
            scanf("%d%d", &u, &v);
            graph[u].push_back(v);
            graph[v].push_back(u);
        }
        dfs(1, 0);
        printf("%lld\n", max(f[1][0], f[1][1]));
    }
    return 0;
}