首先有一个暴力解，我们可以枚举树上的任意两个点，然后统计他们之间的颜色唯一的边数，时间复杂度\(O(n^2)\)。
换个角度，从每条边的贡献出发，每条边产生贡献一定是路径上只有这一条边是该颜色，我们可以把边按照颜色进行分类，强行规定只选这一种颜色的时候，可以产生的贡献。比如当前枚举到了颜色\(1\)，那么我们可以枚举颜色\(1\)内部的每一条边，然后看这条边对所有不连\(1\)颜色的边的点的联通块的贡献，我们设该边连接\(x,y\)两点，那么贡献就是\(x\)所在联通块大小乘上\(y\)所在联通块大小。
那么我们需要依次枚举每一种颜色，然后固定不选这一种颜色，其他颜色的边都连上，这个颜色的所有边贡献计算完之后，连上该颜色的所有边。再让下一个颜色的边不连，固定不选这一种颜色，其他颜色的边都连上，计算这个颜色的所有边贡献...以此类推。我们可以用线段树分治+可撤销并查集实现这个操作，我们让颜色为\(w\)的边在枚举颜色为\([1,w-1],w[i+1,n]\)时生效。当递归到每一个叶子节点的时候，我们需要枚举该叶子节点对应颜色的每一条边，计算贡献。因为一个颜色的一条边在值域为\(n\)的线段树上至多被拆成\(\log(n)\)个区间，有\((n-1)\)条边，在线段树上当前走到一个节点的时候我们需要合并联通块，合并时并查集查询复杂度\(O(n\log n)\)，总的时间复杂度\(O(n\log n)\)。
代码
#include <bits/stdc++.h>
using namespace std;
#define ll long long const int N=5e5+10;
int p[N],siz[N];#define ls (u<<1)
#define rs (u<<1|1)
#define mid ((l+r)>>1)struct Edge{int x,y;
};
stack<Edge> stk;
ll ans=0,n;
int a[N],b[N],w[N];
vector<int> tr[N<<2];
vector<Edge> e[N];//每个权值的所有边int find(int x){return p[x]==x?x:find(p[x]);
}void unite(int x,int y){int fx=find(x),fy=find(y);if(fx^fy){if(siz[fy]>siz[fx]) swap(fx,fy);siz[fx]+=siz[fy];p[fy]=fx;stk.push({fx,fy});}
}void insert(int u,int l,int r,int jl,int jr,int i){if(l>jr||r<jl) return ;if(jl<=l&&r<=jr) return tr[u].push_back(i);insert(ls,l,mid,jl,jr,i);insert(rs,mid+1,r,jl,jr,i);
}void solve(int u,int l,int r){int now=stk.size();for(int i:tr[u]){unite(a[i],b[i]);}if(l==r){for(auto [x,y]:e[l]){int fx=find(x),fy=find(y);ans+=siz[fx]*siz[fy];}}else{solve(ls,l,mid);solve(rs,mid+1,r);}while(stk.size()>now){auto [x,y]=stk.top();stk.pop();siz[x]-=siz[y];p[y]=y;}
}int main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cin>>n;for(int i=1;i<=n;i++) p[i]=i,siz[i]=1;for(int i=1;i<=n;i++){cin>>a[i]>>b[i]>>w[i];e[w[i]].push_back({a[i],b[i]});insert(1,1,n,1,w[i]-1,i);insert(1,1,n,w[i]+1,n,i);}solve(1,1,n);cout<<ans;return 0;
}
总结：直接计算困难的时候，考虑通过贡献进行计算。面对频繁的查询某一个时刻的信息并，可以采用线段树分治结合可撤销并查集解决