【MST+枚举+组合数学】ABC214 D - Sum of Maximum Weights

﹏ヽ暗。殇╰゛Y 2024-03-22 11:08 92阅读 0赞

**本来以为这道题一定是树形DP，然后设状态设了半天发现怎么都转移不出来，然后就不会了**

**事实上这是道枚举题，并且利用了MST的特殊性**

题意：

![9fd7cd63fe7a4bbf9ce42e5336e43007.png][]

思路：

因为N^2枚举两个结点一定会超时，因此考虑改变枚举对象，我们去枚举边，然后对于每条边都去计算贡献

对于每一条边，当它作为最大边时，贡献就应该加上该边一段结点个数\*另一端结点个数

那么，怎么让它作为最大边呢？

这个非常经典，在今天刚做的某一道题中也碰到过了

就是去考虑Kruskal的过程就好了

边Kruskal边计算贡献

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=1e5+10;
    const int mxe=1e5+10;
    
    struct ty{
    	int u,v,w;
    }e[mxe<<2];
    
    int N,u,v,w;
    int sz[mxn],f[mxn];
    
    bool cmp(ty x,ty y){
    	return x.w<y.w;
    }
    int find(int x){
    	return f[x]=(x==f[x])?x:find(f[x]);
    }
    void join(int u,int v){
    	int f1=find(u),f2=find(v);
    	if(f1!=f2) f[f1]=f2,sz[f2]+=sz[f1];
    }
    void solve(){
    	cin>>N;
    	for(int i=1;i<=N;i++){
    		f[i]=i;
    		sz[i]=1;
    	}
    	for(int i=1;i<=N-1;i++){
    		cin>>u>>v>>w;
    		e[i]={u,v,w};
    	}
    	sort(e+1,e+1+N-1,cmp);
    	int ans=0;
    	for(int i=1;i<=N-1;i++){
    		int x=find(e[i].u),y=find(e[i].v);
    		ans+=sz[x]*sz[y]*e[i].w;
    		join(e[i].u,e[i].v);
    	}
    	cout<<ans<<'\n';
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;//cin>>__;
    	while(__--)solve();return 0;
    }

[9fd7cd63fe7a4bbf9ce42e5336e43007.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/4fe0a2e49c59488cb2df481711e87c94.png