Subtask 1: Trâu O(n^3)

Subtask 2:

Gọi ~d(u, v)~ là số lượng cạnh trên đường đi từ ~u \rightarrow v~.

~\Rightarrow~ Độ đẹp của cây sẽ là ~(d(u, v)-g(u, v))~ với mọi ~u, v(u < v)~ và ~g(u, v)~ là số lượng trọng số chỉ xuất hiện 1 lần.

~\Rightarrow~ Bài toán trở thành tính tổng của các ~g(u, v)~ trên 1 mảng bình thường.

~\Rightarrow~ Để tính tổng này nhanh ta có hể làm như sau: ~For(1 \rightarrow n)~ ~ans+=(next[i]-i)*(i-pre[i]).~

~Next[i]=j~ với ~j~ nhỏ nhất mà ~i<j~ và ~w[i]=w[j]~.</p>

~Pre[i]=j~ với ~j~ lớn nhất mà ~i>j~ và ~w[i]=w[j]~.

Subtask 3: Từ ý tưởng của sub2.

Để tính tổng của các ~g(u, v)~ ta có thể làm như sau: Với mỗi số ~x~ là trọng số của cạnh bất kì ta sẽ dsu ghép nó với 2 thành phần liên thông khác không chứa ~x~. Rồi từ đó ta làm như ý tưởng chia để tri với 2 thành phần liên thông như thế. Khi ta ghép đc một cạnh ~x~ ta có thể tăng ans lên ~size1 * size2~ là hai cái size của 2 thành phần liên thông ta ghép được.

Rồi ta chỉ cần xét mọi ~x~ và làm như đã nói. Đpt: O(~n.logn^2~) để có được độ phức tạp này ta cần sử dụng dsu rollback.

Còn để tính tổng của các ~d(u, v)~ ta có thể dp on tree hoặc nhiều cách khác.

#include <bits/stdc++.h>
#define el '\n'
#define fi first
#define sc second
#define int ll
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
using namespace std;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
const int mod=1e9+7;
const int N=1e6+11;
int n, par[N], ans, res, f[N];
struct eg
{
    int u,v,w;
} e[N];
vector<pii> tree;
vector<int> val[N], adj[N];
int finds(int x)
{
    while(par[x]>0) x=par[x];
    return x;
}
void dsu(int a,int b)
{
    a=finds(a);
    b=finds(b);
    if(par[a]>par[b]) swap(a,b);
    tree.push_back({b,par[b]});
    par[a]+=par[b];
    par[b]=a;
}
void rollback()
{
    pair<int,int> c=tree.back();
    tree.pop_back();
    par[par[c.fi]]-=c.sc;
    par[c.fi]=c.sc;
}
void dnc(int l,int r)
{
    if(l==r)
    {
        for(int i:val[l])
        {
            int u=finds(e[i].u);
            int v=finds(e[i].v);
            ans+=par[u]*par[v];
        }
        return;
    }
    int mid=(l+r)/2;
    int mark=tree.size();
    for(int i=mid+1; i<=r; i++)
    {
        for(int j:val[i])
        {
            dsu(e[j].u, e[j].v);
        }
    }
    dnc(l, mid);
    while(tree.size()>mark) rollback();

    for(int i=l; i<=mid; i++)
    {
        for(int j:val[i])
        {
            dsu(e[j].u,e[j].v);
        }
    }
    dnc(mid+1, r);
    while(tree.size()>mark) rollback();
}

int dfs(int u, int p)
{
    int sz=1;
    for(auto v:adj[u])
    {
        if(v!=p)
        {
            int s=dfs(v, u);
            res+=s*(n-s);
            sz+=s;
        }
    }
    return sz;
}
void sol()
{
    cin >> n;
    for(int i=1; i<n; i++)
    {
        cin >> e[i].u >> e[i].v >> e[i].w;
        val[e[i].w].push_back(i);
        adj[e[i].u].push_back(e[i].v);
        adj[e[i].v].push_back(e[i].u);
    }
    memset(par, -1, sizeof par);
    for(int i=1; i<=n; i++) f[i]=1;
    dfs(1, 0);
    dnc(1, n);
//    cout << res << el;
    cout << res-ans << el;
//    cout << ans;
}
signed main()
{
//    freopen("divisor.INP", "r", stdin);
//    freopen("divisor.OUT", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t=1;
    //cin >> t;
    while(t--)
    {
        sol();
    }
}