题目描述

难度分:$1341$

输入$n(2 \leq n \leq 100000)$和一棵树的$n-1$条边（节点编号从$1$开始），每条边包含$3$个数$a$、$b$ 、$c$，表示有一条边权为$c(1 \leq c \leq 10^7)$的边连接$a$和$b$。

定义$f(x,y)$表示从$x$到$y$的简单路径上的最大边权。

输出所有$f(i,j)$的和，其中$i \lt j$。

输入样例$1$

3
1 2 10
2 3 20

输出样例$1$

50

输入样例$2$

5
1 2 1
2 3 2
4 2 5
3 5 14

输出样例$2$

76

算法

并查集

这个题还是比较简单的，很容易想到按照边权从小到大往图里加边的做法。在往图中加边连接节点$a$和$b$时，设$a$所在的组有$sz_a$个元素，$b$所在的组有$sz_b$个元素，此时由于边是按照升序遍历，且整张图是一棵树，节点之间的路径是唯一的，则$a$所在组的所有节点都能与$b$所在组的所有节点连通，交叉组合就能对答案产生$sz_a \times sz_b \times c$的贡献。

复杂度分析

时间复杂度

遍历每条边的时候都会进行集合合并，将并查集的合并操作看做$O(logn)$级别，则算法的时间复杂度为$O(nlogn)$。

空间复杂度

额外空间就是并查集的根节点数组，以及每个节点所在集合的大小数组，两者都是$O(n)$级别的，因此额外空间复杂度为$O(n)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long LL;

const int N = 100010;
int n, p[N], sz[N];

struct Edge {
    int a, b, w;
    bool operator<(const Edge& other) const {
        return w < other.w;
    }
}edges[N];

int find(int x) {
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

void merge(int x, int y) {
    int rx = find(x), ry = find(y);
    if(rx != ry) {
        p[rx] = ry;
        sz[ry] += sz[rx];
    }
}

int main() {
    scanf("%d", &n);
    for(int i = 1; i < n; i++) {
        scanf("%d%d%d", &edges[i].a, &edges[i].b, &edges[i].w);
        p[i] = i;
        sz[i] = 1;
    }
    p[n] = n;
    sz[n] = 1;
    sort(edges + 1, edges + n);
    LL ans = 0;
    for(int i = 1; i < n; i++) {
        int u = edges[i].a, v = edges[i].b, w = edges[i].w;
        LL cnt1 = sz[find(u)], cnt2 = sz[find(v)];
        ans += cnt1*cnt2*w;
        merge(u, v);
    }
    printf("%lld\n", ans);
    return 0;
}