题意

使用 openssl enc -aes256 -pbkdf2 加密

U2FsdGVkX19KpjL7PcdGYvAxd4pyV/Fn2nvUYdCx+VwOkTtxd6plngdvuUPCrE45
LuJSweTHKpER8eDgRfqHc/9OTkDQ6hpcGD1ECnWHmiT4WI+THLFRboSCExzrYu7f
p9jyU2KdsvnMAr9v6xquDMpM+qFCZHGIYn+nGD1ncdpm140S+plTsl3IHIvrN3LC
YtUGl2BKNiEv5hrYAU5nNI/09Qzjp5jfGTJ5igIPcnZlzZSeD8s21gbzgMa6+aVJ
I8iNDv5HX/GrzYucL/JbD2EcGzBNDEfiAra3No0qv9RjBvPiqxajsy8jIftsPkWo
XCDwxaXdQq15IMpcR77DUZH/CGM6FjW3eTSjsKkqZFOdxNMzhLerMNPu4UDgT3lk
/w5vGFCC6oEkddTokRZ6jUdNHKRLY9Umqqws4pBwJk6dEEafNIdrZu3T0TlrUEVg
Qp98/4mu/fRbRKBccqVthnfa4uSC49QOrWaQAGIuYegnVOxtvVl623akuYxBnyic
Fdx6PILI2qNcCEiyqVDSW4bhCCQ8LO3fvcWwT4jIfbwHTcQmE8A4TEEfXtTSWV/f
kJvu9guQCah6j1tI2qOx/XU+0lnCMFm6lQ3iNvVVausnsnP+xIUmBX/6oxf8pDrF
6Na6e7sU/iRz7aZ4nzgTHA==

generator

#!/usr/bin/python3

import sys
import random

if len(sys.argv) != 4:
    print(f'Usage: {sys.argv[0]} n q seed')
    sys.exit(-1)

MAXA = 1000
MAXC = 10**9

n = int(sys.argv[1])
q = int(sys.argv[2])

random.seed(sys.argv[3])

print(n, q)

a = (random.randint(1, MAXA) for i in range(n - 1))
c = (random.randint(1, MAXC) for i in range(n))
print(*a)
print(*c)

for i in range(q):
    x, y = (random.randint(1, n) for i in range(2))
    print(x, y)

解析

我们认为求解乘法逆元是常数复杂度的。

定义 s(i)=∑0≤j<iais(i) = \sum\limits_{0 \le j < i}a_i，即 aa 的前缀和

初始的 n 三方做法

定义 l(x,y)l(x, y) 表示 xx 到 yy 的期望距离。首先，当 x=yx = y 时，l(x,y)=0l(x, y) = 0，因为两点重合。由于 l(x,y)l(x, y) 显然等于 l(y,x)l(y, x)，所以我们可以假设 x<yx < y。因为我们是按照从 00 到 n−1n - 1 的顺序加的点，所以 yy 不可能是 xx 的祖先，也就是说 lca⁡(x,y)\operatorname{lca}(x, y) 一定不等于 yy。枚举 yy 的所有父亲 ii，则 l(x,i)l(x, i) 再加上 ii 到 yy 的边权就是 l(x,y)l(x, y)。

形式化的说：

l(x,y)={0x=yf(y,x)x>y∑0≤i<yai×[f(x,i)+ci]s(y)+cy其他l(x, y) = \begin{cases} 0 & x = y \\ f(y, x) & x > y \\ \frac{\sum\limits_{0 \le i < y}a_i \times [f(x, i) + c_i]}{s(y)} + c_y & \text{其他} \end{cases}

然后按照这个式子递归下去就是 O(n3)O(n^3) 做法，可以考虑前缀和优化一下到 O(n2)O(n^2)，不过这不是重点。

改进

原来的 l(x,y)l(x, y)，就状态定义就是 O(n2)O(n^2) 种，比较难优化，考虑拆分一下。我们知道树上 xx 到 yy 的距离等于 xx 到根的距离加 yy 到根的距离减去 22 倍 lca⁡(x,y)\operatorname{lca}(x, y) 到根的距离。放到期望也是一样的，我们定义 d(x)d(x) 表示 xx 到根的期望距离，f(x,y)f(x, y) 表示 lca⁡(x,y)\operatorname{lca}(x, y) 到根的距离，则 l(x,y)=d(x)+d(y)−2f(x,y)l(x, y) = d(x) + d(y) - 2f(x, y)。这样拆分降低了耦合度。

求解 d(x)

和求 l(x,y)l(x, y) 的方法类似，枚举 xx 的父亲 ii，然后把 d(i)d(i) 加上 ii 到 xx 的边权。容易得到：

d(x)={0x=0∑0≤i<xai×[d(i)+ci]s(i)+cx其他d(x) = \begin{cases} 0 & x = 0 \\ \frac{\sum\limits_{0 \le i < x}a_i \times [d(i) + c_i]}{s(i)} + c_x & \text{其他} \end{cases}

可以维护 ∑0≤i<xai×[d(i)+ci]\sum\limits_{0 \le i < x}a_i \times [d(i) + c_i] 做到 O(n)O(n) 求解。

求解 f(x, y)

仍然和求 l(x,y)l(x, y) 的方法类似，仍然是假设 x<yx < y，枚举 yy 的父亲 ii，由于 yy 不是 xx 的祖先，所以如果 yy 的父亲为 ii，则 lca⁡\operatorname{lca} 到根距离的期望就是 f(x,i)f(x, i)。容易得到：

f(x,y)={d(x)x=yf(y,x)x>y∑0≤i<yai×f(x,i)s(y)其他f(x, y) = \begin{cases} d(x) & x = y \\ f(y, x) & x > y \\ \frac{\sum\limits_{0 \le i < y}a_i \times f(x, i)}{s(y)} & \text{其他} \end{cases}

但直接按这个式子递归和求 l(x,y)l(x, y) 没有什么本质区别，状态也还是 O(n2)O(n^2) 的。我们可以感性猜测一下，因为 yy 是在 xx 后加入的节点，lca⁡(x,y)\operatorname{lca}(x, y) 一定在 xx 到根的链上，所以 f(x,y)f(x, y) 和 yy 很可能没什么关系。我们考查 f(x,y)f(x, y) 和 f(x,y+1)f(x, y + 1) 之间的关系。

f(x,y)=∑0≤i<yai×f(x,i)s(y)f(x,y+1)=∑0≤i<yai×f(x,i)+ai×f(x,y)s(y)+ay\begin{aligned} f(x, y) &= \frac{\sum\limits_{0 \le i < y}a_i \times f(x, i)}{s(y)} \\ f(x, y + 1) &= \frac{\sum\limits_{0 \le i < y}a_i \times f(x, i) + a_i \times f(x, y)}{s(y) + a_y} \end{aligned}

为了方便，我们令 T=∑0≤i<yai×f(x,i)T = \sum\limits_{0 \le i < y}a_i \times f(x, i)，则上式可记作：

f(x,y)=Ts(y)f(x,y+1)=T+ay×f(x,y)s(y)+ay\begin{aligned} f(x, y) &= \frac{T}{s(y)} \\ f(x, y + 1) &= \frac{T + a_y \times f(x, y)}{s(y) + a_y} \end{aligned}

化简 f(x,y+1)f(x, y + 1)：

f(x,y+1)=T+ay×f(x,y)s(y)+ay=T+Ts(y)×ays(y)+ay=T×[s(y)+ay]s(y)×[s(y)+ay]=Ts(y)=f(x,y)\begin{aligned} f(x, y + 1) &= \frac{T + a_y \times f(x, y)}{s(y) + a_y} \\ &= \frac{T + \frac{T}{s(y)} \times a_y}{s(y) + a_y} \\ &= \frac{T \times [s(y) + a_y]}{s(y)\times [s(y) + a_y]} \\ &= \frac{T}{s(y)} \\ &= f(x, y) \end{aligned}

故当 x<yx < y 且 x<zx < z 时，f(x,y)=f(x,z)f(x, y) = f(x, z)。我们可以把所有的 f(x,y)f(x, y) 表示成 f(x,x+1)f(x, x + 1)。形式化的说：

f(x,y)={d(x)x=yf(y,x)x>yf(x,x+1)x+1<yax×d(x)+∑0≤i<xai×f(x,i)s(y)x+1=yf(x, y) = \begin{cases} d(x) & x = y \\ f(y, x) & x > y \\ f(x, x + 1) & x + 1 < y \\ \frac{a_x \times d(x) + \sum\limits_{0 \le i < x}a_i \times f(x, i)}{s(y)} & x + 1 = y \end{cases}

现在状态就只有 O(n)O(n) 的需要求解了，令 g(x)=f(x,x+1)g(x) = f(x, x + 1)，维护 ∑0≤i<xai×f(x,i)\sum\limits_{0 \le i < x}a_i \times f(x, i) 便可以 O(n)O(n) 求解 gg。

实现

using mint = static_modint<1'000'000'007>;

auto get_d(const auto &a, const auto &sa, const auto &c)
{
	const int n = a.size();
	std::vector<mint> d(n);
	mint sd = 0;
	d[0] = 0;
	sd += mint{c[0]} * a[0];
	for (int i = 1; i < n; i++) {
		d[i] = sd / sa[i] + c[i];
		sd += (d[i] + c[i]) * a[i];
	}
	return d;
}

// g(i) = f(i, i + 1)
auto get_g(const auto &a, const auto &sa, const auto &d)
{
	const int n = a.size();
	std::vector<mint> g(n);
	mint s = 0;
	for (int i = 0; i + 1 < n; i++) {
		g[i] = (d[i] * a[i] + s) / sa[i + 1];
		s += g[i] * a[i];
	}
	return g;
};

int main()
{
	int n, q;
	scanf("%d%d", &n, &q);
	std::vector<int> a(n), c(n);
	for (int i = 0; i < n - 1; i++) scanf("%d", &a[i]);
	for (auto &i : c) scanf("%d", &i);
	
	std::vector<mint> sa(n);
	for (int i = 0; i < n - 1; i++) sa[i + 1] = sa[i] + a[i];

	const auto d = get_d(a, sa, c);
	const auto g = get_g(a, sa, d);

	for (int i = 0; i < q; i++) {
		int x, y;
		scanf("%d%d", &x, &y);
		x--;
		y--;
		if (x == y) {
			puts("0");
		} else {
			int t = std::min(x, y);
			printf("%d\n", (d[x] + d[y] - g[t] * 2).val());
		}
	}
}