直接贺 lct 维护 mst 的代码。
思路
观察到 ，考虑分开建 个图表示边权小于等于 的边组成的图。连并查集，记录当前图连了 条边。
可以发现第 个图是第 个图的子图。所以差分 可以得到原图的最小生成树中边权为 的边数。
复杂度 。
code
int n,m;
int f[11][maxn],siz[11];
int fd(int id,int x){
if(f[id][x]==x)return x;
return f[id][x]=fd(id,f[id][x]);
}
void work(){
n=read();m=read();
for(int i=1;i<=10;i++)for(int j=1;j<=n;j++)f[i][j]=j;
for(int i=1;i<n;i++){
int u=read(),v=read(),w=read();
for(int j=w;j<=10;j++)if(fd(j,u)!=fd(j,v))f[j][fd(j,u)]=fd(j,v),siz[j]++;
}
for(int i=1;i<=m;i++){
int u=read(),v=read(),w=read();
for(int j=w;j<=10;j++)if(fd(j,u)!=fd(j,v))f[j][fd(j,u)]=fd(j,v),siz[j]++;
int ans=0;
for(int j=1;j<=10;j++)ans+=(siz[j]-siz[j-1])*j;
printf("%lld\n",ans);
}
}