时间复杂度应该是正确的 $O(m\sqrt q\log n)$，但是不知道为什么跑的这么慢。

#include<bits/stdc++.h>
using namespace std;
using ui=unsigned int;
using ll=long long;
using ull=unsigned long long;
using i128=__int128;
using u128=__uint128_t;
constexpr int N=2e5+5,mod=1e9+7;
inline ll qpow(ll a,ll b){
	ll res=1;
	for(;b;b>>=1,a=a*a%mod)
		if(b&1)res=res*a%mod;
	return res;
}
int n,m,q,a[N],U[N],V[N];ll ans[N];
int siz,tot,pos[N],L[N],R[N];
struct node{
	int l,r,id;
	node(){l=r=0;}
	node(int _l,int _r,int _id){l=_l,r=_r,id=_id;}
	inline bool operator <(const node &_)const&{return pos[l]!=pos[_.l]?l<_.l:r<_.r;}
};
node qry[N];
int f[N],s[N];ll sum[N],res;
int stx[N],sty[N],top;
void clear(){
	res=top=0;
	for(int i=1;i<=n;i++)f[i]=i,s[i]=1,sum[i]=a[i];
}
inline int get(int x){
	while(f[x]!=x)x=f[x];
	return x;
}
inline void merge(int x,int y){
	x=get(x),y=get(y);
	if(x==y)return;
	if(s[x]>s[y])swap(x,y);
	++top,stx[top]=x,sty[top]=y;
	res=(res+sum[x]*sum[y])%mod;
	f[x]=y,s[y]+=s[x],sum[y]=(sum[y]+sum[x])%mod;
}
void undo(int t){
	while(top>t){
		int x=stx[top],y=sty[top];top--;
		f[x]=x,s[y]-=s[x],sum[y]=(sum[y]-sum[x]+mod)%mod;
		res=(res-sum[x]*sum[y]%mod+mod)%mod;
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>m>>q;
	siz=max(1,(int)(m/sqrt(q))),tot=n/siz;
	for(int i=1;i<=tot;i++)
		L[i]=R[i-1]+1,R[i]=L[i]+siz-1;
	if(R[tot]<n)
		++tot,L[tot]=R[tot-1]+1,R[tot]=n;
	for(int i=1;i<=tot;i++)
		for(int j=L[i];j<=R[i];j++)
			pos[j]=i;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=m;i++)cin>>U[i]>>V[i];
	for(int i=1;i<=q;i++)cin>>qry[i].l>>qry[i].r,qry[i].id=i;
	sort(qry+1,qry+q+1);
	clear();
	int l=1,r=0,cur=0;
	for(int i=1;i<=q;i++){
		int cl=qry[i].l,cr=qry[i].r;
		if(pos[cl]!=cur){
			cur=pos[cl];
			l=R[cur]+1,r=l-1;
			undo(0);
		}
		if(cur==pos[cr]){
			for(int j=cl;j<=cr;j++)merge(U[j],V[j]);
			ans[qry[i].id]=res;
			undo(0);
		}
		else{
			while(r<cr)++r,merge(U[r],V[r]);
			int tmp=top;
			while(l>cl)--l,merge(U[l],V[l]);
			ans[qry[i].id]=res;
			undo(tmp),l=R[cur]+1;
		}
	}
	ll inv=qpow((n*(n-1ll)>>1)%mod,mod-2);
	for(int i=1;i<=q;i++)cout<<ans[i]*inv%mod<<'\n';
	return 0;
}