题意：
给出一个无向连通图，里面的点分为0号点和1号点，第i条边的边权是2的i次。
询问所有1号点到0号点的最短路径之和。
题解：
如果对所有1号点跑dijkstra算法，时间肯定是无法接受的。
观察到题目的边权有一个关键的性质，第i条边权是2的i次，这说明前i-1条边加起来都没这条边的边权大。
猜想，所有最短路径都在这个图的最小生成树上。
所以先建立最小生成树，树上的所有边对答案都是有贡献的，现在考虑单边对答案的贡献。我们可以用一遍DFS处理出每条边左边的1号点个数、右边的0号点个数，两者相乘再乘上这条边的权值，左右相反同理，这样就可以算出单边对答案的贡献。
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=2e5+100; const int mod=1e9+7; const ll inf=1e18; typedef long long ll; struct node { int u,v; ll w; int nxt; }edge[maxn]; int head[maxn]; int tot; void addedge (int u,int v,int w) { edge[tot].u=u; edge[tot].v=v; edge[tot].w=w; edge[tot].nxt=head[u]; head[u]=tot++; edge[tot].u=v; edge[tot].v=u; edge[tot].w=w; edge[tot].nxt=head[v]; head[v]=tot++; } ll w[maxn]; int a[maxn];//节点权值 int father[maxn]; int findfather (int x) { int a=x; while (x!=father[x]) x=father[x]; while (a!=father[a]) { int z=a; a=father[a]; father[z]=x; } return x; } ll lst[maxn];//每个节点和他父亲连的那条边 int dfn[2][maxn]; int dfo[2][maxn]; int cnt[2]; int wjm[2][maxn]; void dfs (int u,int pre) { cnt[a[u]]++; dfn[0][u]=cnt[0]; dfn[1][u]=cnt[1]; for (int i=head[u];i!=-1;i=edge[i].nxt) { int v=edge[i].v; if (v==pre) continue; lst[v]=edge[i].w; dfs(v,u); } dfo[0][u]=cnt[0]; dfo[1][u]=cnt[1]; } int main () { w[0]=1; for (int i=1;i<maxn;i++) w[i]=(w[i-1]*2)%mod; int t,n,m; scanf("%d",&t); while (t--) { scanf("%d%d",&n,&m); for (int i=0;i<=n;i++) head[i]=-1; tot=0; int sum[2]; memset(sum,0,sizeof(sum)); cnt[0]=0; cnt[1]=0; for (int i=1;i<=n;i++) scanf("%d",a+i),father[i]=i,sum[a[i]]++,wjm[0][i]=0,wjm[1][i]=0,lst[i]=0; for (int i=1;i<=m;i++) { int u,v; scanf("%d%d",&u,&v); int faU=findfather(u); int faV=findfather(v); if (faU==faV) continue; father[faU]=faV; addedge(u,v,w[i]); } ll ans=0; dfs(1,0); for (int i=1;i<=n;i++) { //每个点与他父亲连接的边的贡献 wjm[0][i]=dfo[0][i]-dfn[0][i]; wjm[1][i]=dfo[1][i]-dfn[1][i]; wjm[a[i]][i]++; ll x=wjm[0][i];//子树里0号点 ll y=sum[1]-wjm[1][i];//除子树外的1号点 ll x1=wjm[1][i];//子树里1号点 ll y1=sum[0]-wjm[0][i];//除子树外0号点 ans=ans+(lst[i]*x%mod)*y%mod+(lst[i]*x1%mod)*y1%mod; ans%=mod; } printf("%lld ",ans); } }