喵哈喽~ 主人！今天我们来解决一个关于守卫黄金的有趣问题喵！诺丁汉郡长需要我们的帮助来对抗罗宾汉，保护他的财宝。让我们一起来看看怎么用聪明的策略帮他保住最多的黄金吧！

F. Sheriff's Defense

---

题目大意

简单来说，我们有一棵由 n 个营地和 n-1 条小径组成的树，每个营地 i 最初有 a[i] 的黄金，喵。

郡长可以选择加固 (strengthen) 任意数量的营地。加固一个营地 u 会产生一个效果：u 的所有相邻营地 v 都会失去 c 的黄金。加固操作本身不会改变 u 自己的黄金数量。

在罗宾汉攻击之后，只有被加固的营地能够幸存下来，其他营地都会被摧毁。我们的任务是，选择一个最优的加固方案，使得所有幸存营地（也就是被加固的营地）的黄金总和最大。一个营地最终的黄金数量是它初始的黄金数量，减去因其邻居被加固而损失的部分。

举个例子，如果营地 i 被加固了，它的邻居 j 和 k 也被加固了，那么营地 i 幸存下来，它最终的黄金是 a[i] - 2*c。如果只有 j 被加固，那么 i 最终的黄金就是 a[i] - c。

我们的目标就是求这个最大的黄金总和，喵~

---

题解方法

看到这种在树上做决策、求最优解的问题，喵酱的DNA就动了，这不就是典型的树形动态规划 (Tree DP) 嘛！

我们可以把营地关系看作一棵树。对于树上的每一个节点（营地），我们都有两种选择：

1. 加固这个营地。
2. 不加固这个营地。

这个决定会影响到它的子节点和父节点。因此，我们可以用一次深度优先搜索（DFS）来遍历整棵树，并在回溯的过程中计算出以每个节点为根的子树能获得的最大黄金。

为了做到这一点，我们需要为每个节点 u 定义DP状态：

• dp[u][0]：表示在以 u 为根的子树中，当营地 u 不加固时，能获得的最大黄金总和。
• dp[u][1]：表示在以 u 为根的子树中，当营地 u 加固时，能获得的最大黄金总和。

通过从叶子节点向上计算，我们最终就能得到根节点的 dp 值，从而得到整个问题的答案，喵！

---

题解

首先，我们来仔细分析一下最终的黄金总和是怎么计算的。

假设我们选择了一个营地集合 S 来加固。

• 幸存营地的初始黄金总和是 sum(a[i]) for i in S。
• 现在考虑损失。对于一条连接营地 u 和 v 的小径，如果 u 和 v 都被加固了，那么 u 会因为 v 的加固而损失 c 黄金，v 也会因为 u 的加固而损失 c 黄金。这条边导致的总损失是 2c。
• 如果 u 和 v 中只有一个被加固，那么这条边不会产生损失（因为未被加固的一方不会计入最终总和，而被加固的一方，它的邻居未被加固，所以也不会有损失）。

所以，我们的目标函数是最大化： Σ (a[i] for i in S) - 2 * c * (S中两个端点都被连接的边的数量)

现在，我们来定义DP的状态转移方程：

我们任意选择一个节点（比如节点1）作为根节点，然后进行DFS。对于当前节点 u 和它的父节点 p：

1. 计算 dp[u][0] (不加固 u)

如果 u 不被加固，它对最终的黄金总和贡献为 0。我们只需要考虑它的每个子节点 v 的子树能贡献的最大价值。对于每个子节点 v，我们可以选择加固它（贡献 dp[v][1]）或者不加固它（贡献 dp[v][0]）。我们当然是选择其中较大的那个啦，喵！ 所以，状态转移方程是： dp[u][0] = Σ max(dp[v][0], dp[v][1]) (对所有 u 的子节点 v 求和)

2. 计算 dp[u][1] (加固 u)

如果 u 被加固，它首先会贡献自己的初始黄金 a[u]。然后，我们再考虑它的每个子节点 v 的贡献。

• 如果选择不加固 v，那么 v 的子树贡献 dp[v][0]。此时边 (u, v) 的两个端点只有一个被加固，所以没有 2c 的惩罚。
• 如果选择加固 v，那么 v 的子树贡献 dp[v][1]。但是，因为 u 和 v 都被加固了，我们需要支付 2c 的代价。所以来自 v 子树的净贡献是 dp[v][1] - 2*c。

对于每个子节点 v，我们在这两种选择中取一个最优的，也就是 max(dp[v][0], dp[v][1] - 2*c)。 所以，状态转移方程是： dp[u][1] = a[u] + Σ max(dp[v][0], dp[v][1] - 2*c) (对所有 u 的子节点 v 求和)

3. 边界条件和最终答案

• 对于叶子节点 u，它没有子节点。所以 dp[u][0] = 0，dp[u][1] = a[u]。
• 在DFS结束后，我们回到根节点（比如节点1）。最终的答案就是 max(dp[1][0], dp[1][1])，代表在根节点加固与不加固两种情况下的最优解。如果营地为空，答案当然是0啦。

下面是实现这个思路的代码喵~

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <array>

void solve() {
    int n;
    long long c;
    std::cin >> n >> c;
    
    std::vector<long long> a(n + 1);
    for (int i = 1; i <= n; ++i) {
        std::cin >> a[i];
    }
    
    std::vector<std::vector<int>> adj(n + 1);
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        std::cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    // 如果没有营地，就没有黄金喵
    if (n == 0) {
        std::cout << 0 << "\n";
        return;
    }
    
    // dp[u][0]: u不加固，子树最大黄金
    // dp[u][1]: u加固，子树最大黄金
    std::vector<std::array<long long, 2>> dp(n + 1);
    
    // 使用 std::function 定义一个递归的 lambda 函数
    std::function<void(int, int)> dfs = 
        [&](int u, int p) {
        // 初始化当前节点的DP值
        dp[u][0] = 0;
        dp[u][1] = a[u];
        
        // 遍历所有邻居
        for (int v : adj[u]) {
            if (v == p) continue; // 不走回头路
            
            // 先递归计算子节点的DP值
            dfs(v, u);
            
            // 根据状态转移方程更新当前节点的DP值
            // 如果 u 不加固
            dp[u][0] += std::max(dp[v][0], dp[v][1]);
            
            // 如果 u 加固
            dp[u][1] += std::max(dp[v][0], dp[v][1] - 2 * c);
        }
    };
    
    // 从节点1开始DFS，父节点设为0
    dfs(1, 0);
    
    // 最终答案是根节点两种选择的较大值
    std::cout << std::max(dp[1][0], dp[1][1]) << "\n";
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    
    return 0;
}

---

知识点介绍

树形动态规划 (Tree DP)

树形DP是一种在树状结构上进行动态规划的算法思想，喵。它非常适合解决那些需要为树上每个节点做出决策，并求全局最优解的问题。

核心思想：

1. 自底向上计算：通常通过深度优先搜索（DFS）实现。当DFS访问到一个节点 u 时，它会先递归地访问完 u 的所有子节点。在从子节点的递归调用返回后，子节点的最优解（即DP值）就已经计算出来了。
2. 状态合并：节点 u 利用它所有子节点 v 的DP值，来计算出自身的DP值。这个过程就是状态转移。
3. 状态定义：dp[u][state] 的定义是关键。state 需要包含足够的信息，以便父节点可以根据 u 的状态来计算自己的状态。在这个问题里，state 就是 0 (不加固) 和 1 (加固)，因为 u 是否加固会影响到它和父节点之间的边是否产生 2c 的惩罚。

树形DP的应用非常广泛，比如求解树的最大独立集、树的直径、树的重心等问题。只要问题满足最优子结构和无后效性（即子树的决策不会影响到子树之外的其他不相关子树），就可以考虑使用树形DP来解决，喵！

好啦，这样诺丁汉郡长就能保住最多的黄金啦，喵~ 主人学会了吗？如果还有其他问题，随时可以再来问我哦！