枚举LCA+分类讨论列式子：0111B

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135540375

http://47.92.197.167:5283/contest/447/problem/2

考虑部分分，枚举LCA

先单纯考虑一个点 ii 作为 xx 祖先的概率。打表 / 推式子得 xx 失无关变量。

我们现在预处理了期望深度 depidep_i 和期望祖先 fif_i

然后现在要努力列式子。

对于 xx 要同时是 u,vu,v 的祖先，概率为 fx2f_x^2

对于 y∈[x+1,u](u<v)y\in[x + 1, u](u < v) ，不能同时是祖先，概率为 ∏y=x+1u(1−fy2)\prod_{y = x + 1}^u(1-f_y^2)

uu 不能是 vv 的祖先（ uu 为LCA的情况要额外统计） ，概率为 1−fu1-f_u

因此答案为：

depu+depv−2∑x=1u−1depxfx2∏y=x+1u(1−fy2)(1−fu)−2depufudep_u+dep_v-2\sum_{x=1}^{u-1}dep_xf_x^2\prod_{y = x + 1}^u(1-f_y^2)(1-f_u)-2dep_uf_u

显然中间那坨可以两次前缀和来搞

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL
 #define debug(...) fprintf(stdout, ##__VA_ARGS__)
#else
 #define debug(...) void(0)
#endif
#define int long long
inline int read(){int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
#define fi first
#define se second
//#define M
#define mo (int)(1e9 + 7)
int pw(int a, int b) {
	int ans=1; 
	while(b) {
		if(b&1) ans*=a; 
		a*=a; b>>=1; 
		ans%=mo; a%=mo; 
	}
	return ans; 
}	
inline void Mod(int &a) { if(a>=mo || a<=-mo) a%=mo; if(a<0) a+=mo; }
inline void Add(int &a, int b) { a+=b; Mod(a); }
inline void Mul(int &a, int b) { Mod(b); a*=b; Mod(a); } 
//#define N
int n, m, i, j, k, T, q;

namespace Sol1 {
	#define N 15
	int a[N], c[N], s[N], f[N][N], ans[N][N]; 
	int u, v; 
	void dfs(int x, int p) {
		if(x > n) {
//			debug(">> %lld\n", p); 
			for(int i = 1; i <= n; ++i) 
				for(int j = 1; j <= n; ++j) {
					Add(ans[i][j], f[i][j] %mo * p); 
//					if(i == 1 && j == 3)
//					debug("f[%lld][%lld] = %lld | %lld\n", i, j, f[i][j], ans[i][j]); 
				}
			return ; 
		}
		for(int i = 1; i < x; ++i) {
			for(int j = 1; j < x; ++j) {
				f[x][j] = f[j][x] = f[i][j] + c[i] + c[x]; 
//				debug("f[%lld %lld] = %lld [%lld + %lld]=> %lld\n", x, j, f[i][j], c[i], c[j], f[x][j]); 
			}
			dfs(x + 1, p * a[i] % mo * s[x - 1] % mo); 
		}
	}
	void Main() {
		for(i = 1; i < n; ++i) a[i] = read(), s[i] = s[i - 1] + a[i]; 
		for(i = 1; i < n; ++i) s[i] = pw(s[i], mo - 2); 
		for(i = 1; i <= n; ++i) c[i] = read(); 
		dfs(2, 1); 	
		while(q--) {
			u = read(); v = read(); 
			printf("%lld\n", ans[u][v]); 
		}
	}
	#undef N
}

namespace Sol2 {
	#define N 1000010
	int u, v, a[N], s[N], c[N], f[N], sum, ans, t[N], g[N]; 
	int dep[N]; 
	void Main() {
		for(i = 1; i < n; ++i) a[i] = read(), s[i] = s[i - 1] + a[i], Mod(s[i]); 
		for(i = 1; i < n; ++i) s[i] = pw(s[i], mo - 2); 
		for(i = 1; i <= n; ++i) c[i] = read(); 
		sum = c[1] * a[1]; 
		for(i = 2; i <= n; ++i) {
			dep[i] = sum % mo * s[i - 1] + c[i]; Mod(dep[i]); 
			Add(sum, (dep[i] + c[i]) * a[i]); 
		}
		for(i = 1; i <= n; ++i) debug("%lld ", dep[i]); debug("\n"); 
		g[0] = 1; 
		for(i = 1; i < n; ++i) {
			f[i] = a[i] * s[i]; Mod(f[i]); 
			/*if(i > 1)*/ g[i] = g[i - 1] * (1 - f[i] * f[i] % mo); Mod(g[i]); 
			if(i == 1) f[i] = g[i] = 1; 
			t[i] = f[i] * f[i]; Mod(t[i]); Mul(t[i], pw(g[i], mo - 2)); 
			Mul(t[i], dep[i]); 
			Add(t[i], t[i - 1]); 
			debug("%lld %lld %lld\n", f[i], g[i], t[i]); 
		}
//		debug("--------- %lld\n", q) ; 
		while(q--) {
			u = read(); v = read(); ans = 0; 
			if(u == v) { printf("0\n"); continue; }
			if(u > v) swap(u, v); 
//			ans = t[u - 1] * g[u - 1]; Mod(ans); 
//			for(i = 1; i < u; ++i) {
//				k = dep[i] * f[i] % mo * f[i] % mo; 
////				for(j = i + 1; j <= u - 1; ++j) Mul(k, 1 - f[j] * f[j] % mo); 
//				Mul(k, pw(g[i], mo - 2)); 
//				Mod(k); Add(ans, k); 
//			}
			ans = t[u - 1]; 
			Mul(ans, g[u - 1]); 
			Mul(ans, 1 - f[u]); //Mul(ans, g[u - 1] % mo); 
			Add(ans, dep[u] * f[u] % mo); 
			ans = dep[u] + dep[v] - 2 * ans; Mod(ans); 
			printf("%lld\n", ans); 
		}
	}
	#undef N
}

signed main()
{
	freopen("tree.in", "r", stdin);
	freopen("tree.out", "w", stdout);
//	srand(time(NULL));
//	T=read();
//	while(T--) {
//
//	}
	n = read(); q = read(); 	
//	if(n <= 10) return Sol1 :: Main(), 0; 
	return Sol2 :: Main(), 0; 
	return 0;
}