题解

问题分析

题目要求计算将一棵树的所有边砍断，使树分解为单个节点的最小总损害值。每次砍断一条边的损害值是该边断开后形成的两个连通分量中硬度最大值的和。

核心思路

观察发现，“砍断所有边”的过程可以反向转化为“从单个节点逐步合并成树”的过程。具体来说：

• 初始时，每个节点都是独立的连通分量，每个分量的最大硬度就是节点自身的硬度。
• 合并两个连通分量时，对应的“反向操作”是“不砍断连接它们的边”，而该边的损害值恰好等于合并前两个分量的最大硬度之和。
• 总损害值即为所有边的损害值之和，因此问题转化为：按某种顺序合并所有节点，使合并过程中累加的“两个分量最大硬度之和”最小。

贪心策略：按节点硬度从小到大的顺序处理节点。当处理节点 (u) 时，仅合并 (u) 与已处理的邻接节点（即硬度不大于 (u) 的节点）。这样可保证每次合并时，两个分量的最大硬度尽可能小，从而使总损害值最小。

算法步骤

1. 初始化数据结构：

   • 用并查集（Union-Find）管理连通分量，记录每个分量的最大硬度（maxv）和父节点（f）。
   • 对所有节点按硬度从小到大排序（硬度相同则按节点编号排序）。

2. 构建邻接表：

   • 读入树的边，构建邻接表，并将每个节点的邻接节点按硬度从小到大排序（确保处理时优先访问硬度较小的节点）。

3. 合并连通分量：

   • 按排序后的顺序遍历节点，标记当前节点为“已处理”。
   • 对于当前节点的每个邻接节点，若已处理，则合并两个节点所在的连通分量，并累加两个分量的最大硬度之和到总损害值。

4. 输出结果：累加的总和即为最小总损害值。

正确性证明

• 合并顺序的合理性：按硬度从小到大处理节点时，每次合并的两个分量的最大硬度均不超过当前节点的硬度（因邻接节点已处理，其硬度≤当前节点硬度）。这确保了每条边的损害值在合并时被计算，且此时的最大硬度是最小可能值。
• 总损害值的完整性：树有 (n-1) 条边，合并过程恰好执行 (n-1) 次合并操作，覆盖所有边，因此总损害值是所有边的损害之和。

代码实现

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100000 + 5;

vector<int> G[MAXN];  // 邻接表
int a[MAXN];          // 节点硬度
int node[MAXN];       // 节点编号，用于排序
int f[MAXN];          // 并查集父节点
int maxv[MAXN];       // 每个连通分量的最大硬度
bool vis[MAXN];       // 标记节点是否已处理
int n;
long long ans = 0;    // 总损害值

// 排序比较函数：按硬度从小到大，硬度相同则按节点编号从小到大
bool cmp(int i, int j) {
    return a[i] != a[j] ? (a[i] < a[j]) : (i < j);
}

// 并查集查找（路径压缩）
int find(int k) {
    return k == f[k] ? k : f[k] = find(f[k]);
}

// 合并两个连通分量，累加损害值
void merge(int u, int v) {
    u = find(u);
    v = find(v);
    if (u == v) return;  // 已在同一分量，无需合并
    ans += maxv[u] + maxv[v];  // 累加当前两个分量的最大硬度之和
    maxv[v] = max(maxv[v], maxv[u]);  // 更新合并后分量的最大硬度
    f[u] = v;  // 合并
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        node[i] = i;
        f[i] = i;  // 初始化并查集：父节点为自身
        maxv[i] = a[i];  // 初始分量最大硬度为自身硬度
    }
    // 按硬度排序节点
    sort(node + 1, node + n + 1, cmp);
    
    // 读入边，构建邻接表
    for (int i = 1; i <= n - 1; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    // 每个节点的邻接表按硬度排序
    for (int i = 1; i <= n; i++) {
        sort(G[i].begin(), G[i].end(), cmp);
    }
    
    // 按排序后的节点顺序处理，合并已访问的邻接节点
    for (int i = 1; i <= n; i++) {
        int u = node[i];
        vis[u] = true;  // 标记为已处理
        for (int v : G[u]) {
            if (vis[v]) {  // 仅合并已处理的邻接节点
                merge(u, v);
            }
        }
    }
    
    printf("%lld\n", ans);
    return 0;
}

复杂度分析

• 时间复杂度：(O(n \log n))。排序节点和邻接表的时间为 (O(n \log n))，并查集的查找和合并操作近乎 (O(1))（路径压缩优化），总复杂度为 (O(n \log n))，可满足 (n \leq 10^5) 的数据范围。
• 空间复杂度：(O(n))，用于存储邻接表、并查集等数据结构。