由于我好久都没有独立思考了（抄了好久题解），思维什么的早没有了。

看完题只能想到一种暴力：遍历+LCA

题目给出的是一个最小生成树，我们可以从边入手，把每条边所连的左右两个点分别看做一个集合，

左边集合和右边集合所要连的边数是（cnt[i]*cnt[j]-1），-1是因为要抛去本身这条边

我们要连的边权是多大？比当前的边大，

否则就不满足有且仅有一棵最小生成树T，所以边权就为（当前边的边权+1）

我们可以贪心的去解决，把边从小到大排序，并查集一下就行了，当然还得加上原始边的边权。

另外...ans的开long long

#include
      
       #include
       
        #define ll long longusing namespace std;inline int read(){    int sum = 0,p = 1;    char ch = getchar();    while(ch < '0' || ch > '9')    {        if(ch == '-')            p = -1;        ch = getchar();    }    while(ch >= '0' && ch <= '9')    {        (sum *= 10) += ch - '0';        ch = getchar();    }    return sum * p;}const int N =  1e5 + 5;int n,fa[N],cnt[N];ll ans;struct edge{    int frm,to,wei;}e[N];bool cmp(edge a,edge b){    return a.wei < b.wei;}int findfa(int x){    return fa[x] == x ? x : findfa(fa[x]);} void kruskal(){    for(int i = 1;i <= n;i++)    {        fa[i] = i;        cnt[i] = 1;    }    sort(e+1,e+n,cmp);    for(int i = 1;i <= n - 1;i++)    {        int u = findfa(e[i].frm);        int v = findfa(e[i].to);        if(u == v)            continue;        fa[v] = u;        ans += (ll)(cnt[u] * cnt[v] - 1) * (e[i].wei + 1);        cnt[u] += cnt[v];    }}int main(){    n = read();    for(int i = 1;i <= n - 1;i++)    {        e[i].frm = read();        e[i].to = read();        e[i].wei = read();        ans += (ll)e[i].wei;    }    kruskal();    printf("%lld",ans);    return 0;}