Expected Distance
题目链接:gym102979E
题目大意
有一棵树,第 i 个点的父亲再 1~i-1 中根据每个数的 a 值乘正比概率出现,然后边的长度是两端的点的 b 值的和。
然后多组询问每次问你两个点它们树上的路径期望长度。
思路
首先把树上路径拆成两段的深度减去两倍的 LCA 深度。
考虑求出一个点的期望深度:
\(f_i=\dfrac{\sum\limits_{j=1}^{i-1}a_j(b_i+b_j)}{\sum\limits_{j=1}^{i-1}a_j}\)
这个可以维护这个东西来做:
\(\dfrac{\sum\limits_{j=1}^{i-1}(a_jb_j)}{\sum\limits_{j=1}^{i-1}a_j}\)
然后考虑 LCA,你考虑设 \(g_{x,y}\) 为 \(x,y\) 之间 LCA 的期望深度。
然后你就把深度大的往上跳,那还是小就不管继续,那只有跳到小于或者等于才会要判断。
那我们不难看出跳到的位置的概率就是按它们 \(a_i\) 成正比。
那如果是一样,那就可以结束,进行一个贡献。
否则我们就可以递归下去,这次是小的那个就是你之前大的那个了。
\(g_{x,y}=\dfrac{a_xf_x+\sum\limits_{i=1}^{x-1}a_ig_{i,x}}{\sum\limits_{i=1}^{x}a_i}(x<y)\)
代码
#include<cstdio>
#include<algorithm>
#define ll long long
#define mo 1000000007
using namespace std;
const int N = 3e5 + 100;
int n, q, a[N], b[N], sa[N];
ll f[N], g[N], invs[N];
ll ksm(ll x, ll y) {
ll re = 1;
while (y) {
if (y & 1) re = re * x % mo;
x = x * x % mo; y >>= 1;
}
return re;
}
void make_f() {
ll sum = a[1] * (f[1] + b[1]) % mo;
for (int i = 2; i <= n; i++) {
f[i] = (sum * invs[i - 1] % mo + b[i]) % mo;
(sum += a[i] * (f[i] + b[i]) % mo) %= mo;
}
}
void make_g() {
ll sum = 0;
for (int i = 2; i <= n; i++) {
g[i] = (f[i] * a[i] % mo + sum) % mo * invs[i] % mo;
(sum += g[i] * a[i] % mo) %= mo;
}
}
int main() {
scanf("%d %d", &n, &q);
for (int i = 1; i < n; i++) scanf("%d", &a[i]), sa[i] = sa[i - 1] + a[i], invs[i] = ksm(sa[i], mo - 2);
for (int i = 1; i <= n; i++) scanf("%d", &b[i]);
make_f(); make_g();
for (int i = 1; i <= q; i++) {
int l, r; scanf("%d %d", &l, &r);
if (l > r) swap(l, r);
if (l == r) {printf("0\n"); continue;}
printf("%lld\n", ((f[l] + f[r] - 2ll * g[l]) % mo + mo) % mo);
}
return 0;
}
标签:期望,limits,ll,gym102979E,re,sum,Expected,mo,DP
From: https://www.cnblogs.com/Sakura-TJH/p/gym102979E.html