推一推式子后发现每个点不论走几步被访问到的概率都是 $\frac{d_{i}}{2m}$
code:
#include <cstdio> #include <string> #include <algorithm> #define N 100070 #define ll long long #define mod 1000000007 using namespace std; int a[N],d[N]; namespace IO { void setIO(string s) { string in=s+".in"; string out=s+".out"; freopen(in.c_str(),"r",stdin); } }; ll qpow(ll x,ll y) { ll ans=1; while(y) { if(y&1) ans=ans*x%mod; x=x*x%mod,y>>=1; } return ans; } int main() { // IO::setIO("input"); int n,m,k,i,x,y; ll ans=0; scanf("%d%d%d",&n,&m,&k); for(i=1;i<=n;++i) scanf("%d",&a[i]); for(i=1;i<=m;++i) scanf("%d%d",&x,&y),++d[x],++d[y]; for(i=1;i<=n;++i) ans+=a[i]*d[i]; printf("%lld\n",ans*k%mod*qpow(2*m,mod-2)%mod); return 0; }