哈喽，各位算法爱好者们，喵~ 是我，你们最喜欢的小猫娘！今天也要一起努力攻克算法难题呀！(ฅ'ω'ฅ)

这次我们要解析的题目是 Codeforces 上的 1092F - Tree with Maximum Cost。这可是一道非常经典的树形 DP 问题哦，用到了一个叫做“换根DP”的可爱技巧。别担心，我会一步一步带你弄明白的，喵！

题目大意

我们拿到了一棵有 n 个节点的树。每个节点 v 都有一个权值 a_v。

题目定义了一种 “树的代价” 的计算方式：

1. 首先，我们任选一个节点 v 作为树的根。
2. 然后，树的代价就是所有节点 i 到根节点 v 的距离 dist(i, v) 乘以节点 i 自身的权值 a_i，再把它们全部加起来。 公式长这样：Cost(v) = ∑ (dist(i, v) * a_i)，其中 i 遍历树上所有的节点。

我们的任务就是，从所有可能的根节点中，找到一个能让这个 “树的代价” 达到最大的那个值。

举个栗子，就像题目里的图一样，如果我们选了节点 3 当根，那么：

• 节点 1 到 3 的距离是 2，贡献是 2 * a_1 = 2 * 9 = 18
• 节点 2 到 3 的距离是 1，贡献是 1 * a_2 = 1 * 4 = 4
• 节点 3 到 3 的距离是 0，贡献是 0 * a_3 = 0 * 1 = 0
• ... 以此类推 把所有节点的贡献加起来，就是以 3 为根时的总代价啦。我们要做的就是把每个点都当一次根，算出代价，然后取最大值。

解题思路

最直接的想法是什么呢？当然是把每个节点都当一次根，然后对每个根都做一次 DFS/BFS 来计算它到所有其他节点的距离，最后算出总代价。这样总共有 n 个节点，每次计算代价需要 O(n) 的时间，总时间复杂度就是 O(n^2)。

看一眼数据范围 n <= 2*10^5，O(n^2) 肯定是会超时的，呜...得想个更聪明的办法才行，喵~

这时候，就要请出我们今天的主角——换根DP（也叫二次扫描法）！

换根DP是一种特殊的树形DP，专门解决这类需要“对每个节点都计算一次作为根时的答案”的问题。它的核心思想是：

1. 第一次扫描 (DFS)：先随便选一个点当根（比如节点 1），通过一次从下到上的 DFS，计算出以节点 1 为根时的答案，以及一些辅助信息（比如每个子树的节点权值和）。
2. 第二次扫描 (DFS)：再进行一次从上到下的 DFS，利用父节点已经算好的答案，来快速推导出子节点的答案。这个过程就像是把根从父节点“换”到了子节点，所以叫换根DP，是不是很形象呀？

通过这种方式，我们只需要两次 DFS，总时间复杂度就降到了 O(n)，完美解决问题，喵~

详细题解

好啦，我们来一步步实现这个思路吧！

我们需要一些数组来存放我们的中间结果：

• a[N]: 存储每个节点的权值。
• adj[N]: 邻接表，存树的结构。
• subtree_sum[N]: subtree_sum[u] 表示以 u 为根的子树中所有节点的权值（a_v）之和。
• cost[N]: cost[u] 表示以 u 为根时，整棵树的代价。
• total_sum: 整棵树所有节点的权值总和。

第一步：第一次DFS，固定根计算初始值

我们先假定 节点 1 是根。dfs1(u, p, depth) 的任务就是计算 cost[1] 和所有子树的权值和 subtree_sum。

dfs1(u, p, depth) 的参数：

• u: 当前节点
• p: u 的父节点
• depth: u 的深度（到根节点 1 的距离）

它的工作流程是：

1. 对于当前节点 u，它对 cost[1] 的贡献是 depth * a[u-1]。我们把它累加到 cost[1] 上。
2. 初始化 subtree_sum[u] 为它自己的权值 a[u-1]。
3. 遍历 u 的所有邻居 v，只要 v 不是它的父节点 p，就递归调用 dfs1(v, u, depth + 1)。
4. 当从子节点 v 的递归返回后，说明 v 的子树已经处理完毕，subtree_sum[v] 也已经算好了。这时，我们把 subtree_sum[v] 累加到 subtree_sum[u] 上。

当 dfs1(1, 0, 0) 执行完毕后：

• cost[1] 就得到了以 1 为根时的准确代价。
• subtree_sum 数组被正确填充。

第二步：第二次DFS，换根推导所有节点的代价

现在我们有了 cost[1]，接下来就要从 1 出发，把根“换”到其他节点去。

思考一下，当我们把根从父节点 u 移动到它的一个子节点 v 时，代价会怎么变化呢？

• 对于原来在 v 的子树里的所有节点，它们到新根 v 的距离都比到旧根 u 的距离 减少了 1。这部分节点权值总和是 subtree_sum[v]。所以总代价会减少 1 * subtree_sum[v]。
• 对于原来不在 v 的子树里的所有节点（包括 u 和 u 的其他子树），它们到新根 v 的距离都比到旧根 u 的距离 增加了 1。这部分节点的权值总和是 total_sum - subtree_sum[v]。所以总代价会增加 1 * (total_sum - subtree_sum[v])。

把这两部分变化合起来，我们就得到了从 cost[u] 推导 cost[v] 的神奇公式： cost[v] = cost[u] - subtree_sum[v] + (total_sum - subtree_sum[v]) 化简一下就是： cost[v] = cost[u] + total_sum - 2 * subtree_sum[v]

现在我们可以进行第二次 DFS 了，dfs2(u, p)：

1. 遍历 u 的所有邻居 v，只要 v 不是父节点 p。
2. 利用上面的公式，根据 cost[u] 计算出 cost[v]。
3. 递归调用 dfs2(v, u)，继续向下换根。

当 dfs2(1, 0) 执行完毕后，cost 数组里的所有值就都计算出来啦！

第三步：找到最大值

最后一步就非常简单了，我们只需要遍历 cost 数组（从 cost[1] 到 cost[n]），找到其中的最大值，就是题目的答案了！

下面是完整的 C++ 代码实现，喵~

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

// 为了方便，这里直接用了标准命名空间喵
using namespace std;

// 全局变量，方便DFS函数访问
int n;
vector<long long> a;
vector<vector<int>> adj;
vector<long long> subtree_sum;
vector<long long> cost;
long long total_sum = 0;

// 第一次DFS:
// - 任意选择节点1作为根
// - 计算所有节点的子树权值和 subtree_sum[u]
// - 计算初始根节点1的代价 cost[1]
void dfs1(int u, int p, int depth) {
    // 节点u对cost[1]的贡献
    cost[1] += (long long)depth * a[u - 1];
    
    // 初始化u的子树和为它自己的权值
    subtree_sum[u] = a[u - 1];
    
    // 递归处理所有子节点
    for (int v : adj[u]) {
        if (v != p) {
            dfs1(v, u, depth + 1);
            // 从子节点返回后，把子树的和加到父节点上
            subtree_sum[u] += subtree_sum[v];
        }
    }
}

// 第二次DFS (换根):
// - 从初始根1开始遍历
// - 对于每个节点u，根据cost[u]计算其子节点v的代价cost[v]
// - 公式: cost[v] = cost[u] + total_sum - 2 * subtree_sum[v]
void dfs2(int u, int p) {
    // 为u的每个子节点v计算代价并递归
    for (int v : adj[u]) {
        if (v != p) {
            cost[v] = cost[u] + total_sum - 2 * subtree_sum[v];
            dfs2(v, u);
        }
    }
}

int main() {
    // 快速I/O
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;

    a.resize(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        total_sum += a[i];
    }

    adj.resize(n + 1);
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    // DP数组初始化，节点从1开始
    subtree_sum.resize(n + 1);
    cost.resize(n + 1, 0);

    // 第一步: 从节点1开始DFS，计算初始值
    // 根节点1的父节点设为0（虚拟节点），深度为0
    dfs1(1, 0, 0);

    // 第二步: 第二次DFS，进行换根操作，计算所有节点的代价
    dfs2(1, 0);

    // 第三步: 在所有可能的代价中找到最大值
    cout << *max_element(cost.begin() + 1, cost.end()) << endl;

    return 0;
}

知识点介绍

树形DP (Tree DP)

树形DP是一种在树状结构上进行动态规划的算法。它的特点是，一个节点的DP状态值通常由它的子节点的状态值推导而来。

• 状态定义：dp[u] 通常表示在以 u 为根的子树中，满足某种条件的最优解或方案数。
• 状态转移：通过DFS遍历树，在回溯（从子节点返回到父节点）的过程中，根据子节点的 dp 值来计算父节点的 dp 值。这是一种自底向上的计算过程。

换根DP (Rerooting DP)

换根DP是树形DP的一个进阶技巧，专门解决那些需要“以每个节点为根求解”的问题。它巧妙地将 O(N^2) 的暴力枚举优化到了 O(N)。

它的通用模式就是“二次扫描”：

1. 第一次扫描 (自底向上)：任意指定一个根，通过一次DFS计算出这个根的答案，以及所有子树的一些必要信息（如子树大小、子树和等）。
2. 第二次扫描 (自顶向下)：再通过一次DFS，从我们指定的根出发，利用父节点已经算好的答案和第一次扫描得到的子树信息，快速推导出子节点的答案。这个推导过程就是“换根”的核心。

掌握了换根DP，很多看起来很复杂的树上问题都会变得清晰起来哦！

好啦，今天的题解就到这里啦！希望这篇详细的讲解能帮助你理解换根DP的奥妙。如果还有不明白的地方，可以再多看几遍，或者自己画个小树推演一下过程，一定会豁然开朗的！我们下次再见，喵~ ( ^ω^ )