1.11模拟赛 T2题解

简要题意

每个点有一定概率向前面的点连边，求两点之间距离的期望

思路

推柿子

code

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define N 1000005
int n,m,u,v;
const int mod=1e9+7;
int a[N],sum[N],c[N],dep[N],s[N],f[N],g[N],h[N];
int ksm(int x,int y){
	int ans=1;
	while(y){
		if(y&1) ans=ans*x%mod;
		x=x*x%mod,y>>=1;
	}
	return ans;
}
int mo(int x){
	return (x%mod+mod)%mod;
}
signed main(){
	freopen("tree.in","r",stdin);
	freopen("tree.out","w",stdout);
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<n;i++) scanf("%lld",&a[i]),sum[i]=sum[i-1]+a[i],sum[i]%=mod;
	for(int i=1;i<=n;i++) scanf("%lld",&c[i]);
	dep[1]=0,s[1]=a[1]*c[1]%mod,g[1]=1;
	for(int i=2;i<=n;i++){
		dep[i]=s[i-1]*ksm(sum[i-1],mod-2)%mod+c[i],dep[i]%=mod;
		s[i]=s[i-1]+a[i]*(dep[i]+c[i])%mod,s[i]%=mod;
		f[i]=a[i]*ksm(sum[i],mod-2)%mod;
		g[i]=g[i-1]*(1+mod-f[i]*f[i]%mod)%mod;
		h[i]=h[i-1]+f[i]*f[i]%mod*dep[i]%mod*ksm(g[i],mod-2)%mod,h[i]%=mod;
	}
	while(m--){
		scanf("%lld%lld",&u,&v);
		if(u==v){
			printf("0\n");
			continue;
		}
		if(u>v) swap(u,v);
		printf("%lld\n",mo(dep[u]+dep[v]-2*f[u]*dep[u]%mod-2*g[u-1]%mod*(1+mod-f[u])%mod*h[u-1]%mod));
	}
	return 0;
}