HDU6832 A Very Easy Graph Problem（生成树）

这道题的边权是2的幂次，显然我们发现边权前面所有边相加都不如这条边长，因此其实本题的最短路径就是最小生成树

之后对于答案只需要计算每条边的贡献即可

#include<bits/stdc++.h>
#define getsz(p) (p?p->sz:0)
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int N=3e5+10;
struct node{
    int a,b;
    ll w;
}s[N];
int p[N];
int a[N];
int h[N],e[N],ne[N],idx;
ll w[N];
int cnt1,cnt2;
ll f[N][2];
void add(int a,int b,int c){
    e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
ll qmi(ll a,ll b){
    ll res=1;
    while(b){
        if(b&1){
            res=res*a%mod;
        }
        b>>=1;
        a=a*a%mod;
    }
    return res;
}
int find(int x){
    if(x!=p[x]){
        p[x]=find(p[x]);
    }
    return p[x];
}
ll ans=0;
void dfs(int u,int fa){
    int i;
    if(a[u])
        f[u][1]=1;
    else
        f[u][0]=1;
    for(i=h[u];i!=-1;i=ne[i]){
        int j=e[i];
        if(j==fa)
            continue;
        dfs(j,u);
        f[u][1]+=f[j][1];
        f[u][0]+=f[j][0];
        ans=(ans+w[i]*(f[j][0]*(cnt1-f[j][1])%mod+f[j][1]*(cnt2-f[j][0])%mod)%mod)%mod;
    }
}
int main(){
    ios::sync_with_stdio(false);
    int t;
    cin>>t;
    while(t--){
        int n,m;
        cin>>n>>m;
        int i;
        ans=0;
        cnt1=0;
        cnt2=0;
        memset(h,-1,sizeof h);
        memset(f,0,sizeof f);
        for(i=1;i<=n;i++){
             p[i]=i;
             cin>>a[i];
             if(a[i])
                cnt1++;
             else
                cnt2++;
        }
        for(i=1;i<=m;i++){
            int u,v;
            cin>>u>>v;
            ll w=qmi(2,i);
            s[i]={u,v,w};
        }
        for(i=1;i<=m;i++){
            int pa=find(s[i].a);
            int pb=find(s[i].b);
            if(pa!=pb){
                p[pa]=pb;
                add(s[i].a,s[i].b,s[i].w);
                add(s[i].b,s[i].a,s[i].w);
                p[pa]=pb;
            }
        }
        dfs(1,0);
        cout<<ans<<endl;
    }
    return 0;
}