題意

使用 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());
		}
	}
}