这个题当时打多校的时候有思路，但是代码能力差，没有写出来
事后看zimpha巨巨的题解，看了觉得基本差不多
核心思路：就是找出割点，然后变成森林，然后树形dp就可以搞了
关键就在重新构图上，缩完点以后，一个割点至少在两个点双里面，这个时候
把割点拿出来，分别和点双连边，也就是说，缩完的点双是不包含割点的，这个可以人为搞一下
（像有的点双里面只包含一个桥边，如果把割点拿出来，点双里面没有点了，这个时候把点双的权值积设为1就好）
然后说是树形dp，其实就是逆元搞一搞，这个很简单，树形dp只处理割点的答案
注意：这个图不联通，这是一个点，还有孤立点，我一直wa在孤立点上，（我的点双模板只能解决至少包含两个点的连通图，这个题丰满了我的模板，感谢）
#include <stdio.h> #include <iostream> #include <algorithm> #include <string.h> #include <vector> #include <math.h> #include <stack> #include <map> using namespace std; typedef long long LL; const int N = 1e5+5; const LL mod = 1e9+7; LL qpow(LL a,LL b){ LL ret=1; while(b){ if(b&1)ret=(ret*a)%mod; b>>=1; a=(a*a)%mod; } return ret; } int head[N<<1],tot,T,n,m; struct Edge{ int u,v,next; }edge[N*4]; void addedge(int u,int v){ edge[tot].u=u; edge[tot].v=v; edge[tot].next=head[u]; head[u]=tot++; } int low[N],dfn[N],clk,cnt,belbcc[N]; bool iscut[N]; vector<int>bcc[N],cut; stack<int>s; void init(){ memset(dfn,0,sizeof(dfn)); memset(head,-1,sizeof(head)); memset(belbcc,0,sizeof(belbcc)); tot=clk=cnt=0; cut.clear(); } LL w[N],bccw[N<<1],ret[N],blkw[N<<1],zong; bool vis[N<<1]; int blk,bel[N<<1]; void dfs(int u,int f){ dfn[u]=low[u]=++clk; int child=0; if(head[u]==-1){ ++cnt;bcc[cnt].clear(); bcc[cnt].push_back(u); belbcc[u]=cnt; return ; } for(int i=head[u];~i;i=edge[i].next){ int to=edge[i].v; if(!dfn[to]){ ++child;s.push(i);dfs(to,u); low[u]=min(low[u],low[to]); if(low[to]>=dfn[u]){ iscut[u]=true;++cnt;int x;bcc[cnt].clear(); do{ x=s.top();s.pop(); if(belbcc[edge[x].u]!=cnt){ bcc[cnt].push_back(edge[x].u); belbcc[edge[x].u]=cnt; } if(belbcc[edge[x].v]!=cnt){ bcc[cnt].push_back(edge[x].v); belbcc[edge[x].v]=cnt; } }while(x!=i); } } else if(dfn[to]<dfn[u]&&to!=f){ s.push(i); low[u]=min(low[u],dfn[to]); } } if(!f&&child==1)iscut[u]=false; if(iscut[u])cut.push_back(n+u),bccw[n+u]=w[u]; } void predfs(int u,int f){ bel[u]=blk;blkw[blk]=blkw[blk]*bccw[u]%mod; vis[u]=true; for(int i=head[u];~i;i=edge[i].next){ int v=edge[i].v; if(v==f)continue; predfs(v,u); } } LL treedp(int u,int f){ LL pro=1,sum=0,tmp; vis[u]=false; for(int i=head[u];~i;i=edge[i].next){ int v=edge[i].v; if(v==f)continue; tmp=treedp(v,u); pro=pro*tmp%mod; sum=(sum+tmp)%mod; } pro=pro*bccw[u]%mod; if(u>n){ tmp=blkw[bel[u]]; tmp=tmp*qpow(pro,mod-2)%mod; sum=(sum+tmp)%mod; tmp=zong-blkw[bel[u]]; while(tmp<0)tmp+=mod; ret[u-n]=(sum+tmp)%mod; } return pro; } int main(){ scanf("%d",&T); while(T--){ scanf("%d%d",&n,&m); for(int i=1;i<=n;++i)scanf("%I64d",&w[i]); init(); for(int i=0;i<m;++i){ int u,v;scanf("%d%d",&u,&v); addedge(u,v);addedge(v,u); } for(int i=1;i<=n;++i)if(!dfn[i])dfs(i,0); tot=0;memset(head,-1,sizeof(head)); for(int i=1;i<=cnt;++i){ bccw[i]=1; for(int j=0;j<bcc[i].size();++j){ int u=bcc[i][j]; if(iscut[u]) addedge(i,u+n),addedge(u+n,i); else bccw[i]=bccw[i]*w[u]%mod; } } blk=0; for(int i=1;i<=cnt;++i) if(!vis[i]){++blk;blkw[blk]=1;predfs(i,0);} for(int i=0;i<cut.size();++i) if(!vis[cut[i]]){++blk;blkw[blk]=1;predfs(cut[i],0);} zong=0; for(int i=1;i<=blk;++i)zong=(zong+blkw[i])%mod; for(int i=1;i<=cnt;++i) if(vis[i])treedp(i,0); for(int i=0;i<cut.size();++i) if(vis[cut[i]])treedp(cut[i],0); LL ans=0; for(int i=1;i<=n;++i){ if(iscut[i]){ ans=(ans+1ll*i*ret[i]%mod)%mod; iscut[i]=false; } else{ int k=belbcc[i]; k=bel[k]; LL ad=0; if(w[i]!=blkw[k])ad=blkw[k]*qpow(w[i],mod-2)%mod; LL tmp=zong-blkw[k]; while(tmp<0)tmp+=mod; tmp=(tmp+ad)%mod; ans=(ans+1ll*i*tmp%mod)%mod; } } printf("%I64d ",ans); } return 0; }