ARC195E Sol || 人类智慧 2.0
CarroT1212
·
·
题解
先把 $dis_{u,v}$ 拆成 $dis_u+dis_v-2dis_{\lca{u,v}}$。然后把求所有方案之和改成求期望，现在我们需要解决两个问题：
+ $E(dis_u)$，也就是 $u$ 及其祖先的 $a_i$ 之和的期望。
这个是容易的，$dp_i=a_i+\frac{\sum\limits_{j=1}^{i-1}dp_{j}}{i-1}$ 即可。
+ $E(dis_{\lca{u,v}})$，也就是，同时为 $u$ 和 $v$ 的祖先的点 $p$ 的 $a_p$ 之和的期望。
考虑对于一个询问 $(u,v)$，求每个 $a_p$ 的贡献 $g(p,u,v)$，也就是，$u,v$ 都在 $p$ 的子树内的概率。
先考虑它的子问题：如何求 $u$ 在 $p$ 子树内的概率 $f(p,u)$？
进行一些胡乱尝试之后发现，考虑令 $x:p\to u$，过程中维护 $[p,x]$ 在 $p$ 子树内的期望点数 $b(p,x)$。有 $b(p,p)=1,b(p,x)=b(p,x-1)+\frac{b(p,x-1)}{x-1}=b(p,x-1)\cdot\frac{x}{x-1}$。显然有 $b(p,x)=\frac{x}{p}$。
转移式的解释：相当于一个从 $p$ 往大逐渐加点的过程，每次加点 $x$，如果它要在 $p$ 子树内，就要求它的父亲也是一个在 $p$ 子树内的点，也就是 $p$ 子树中新出现点 $x$ 的概率是 $\frac{b(p,x-1)}{x-1}$。而这个转移确实符合期望线性性！
用这个思路可以得到：$f(p,u)=\frac{b(p,u-1)}{u-1}=\frac{1}{p}$。
（由此可以发现前一个问题的 $dp_i$ 其实等于 $a_i+\sum\limits_{j=1}^{i-1}\frac{a_j}{j}$）
总之 $g(u,u,v)=f(u,v)$ 就是可以轻松求得的了。现在不妨设 $g(p,u,v)$ 有 $p<u<v$ 然后考虑怎么算。
还是尝试类似的转移思路，看起来只要在加入 $u$ 的时候，仅保留 $u$ 在 $p$ 子树里时的贡献即可。
进行和上面一样的转移可以得到 $g(p,u,v)=\frac{b(p,u)}{u}$。所以问题就是求出这个时候 $b(p,u)$ 的值。
> 一个错误示范是直接令 $b(p,u)=b(p,u-1)+1$。根据后面的推导可以发现 $u$ 这里的转移线性性其实被破坏掉了。
正确的求法是 $b(p,u)=\sum\limits_{x}P(x)\cdot \frac{x}{u-1}(x+1)=\sum\limits_{x}P(x)\frac{x^2+x}{u-1}$，其中 $P(x)$ 为 $[p,u-1]$ 中在 $p$ 子树内的点数 $=x$ 的概率。转移式的意义是，一棵 $p$ 子树大小为 $x$ 的树，在加入 $u$ 后，贡献仍然保留（$u$ 在子树内）的概率为 $\frac{x}{u-1}$，加完之后 $p$ 子树大小一定为 $x+1$。
很遗憾的是出现了一个 $P(x)x^2$ 的项，所以需要再设 $c(p,x)$ 表示 $[p,x]$ 在 $p$ 子树内的点数**的平方**的期望。把期望式子拆一下有 $c(p,x)=(\frac{2}{x-1}+1)\cdot c(p,x-1)+\frac{b(p,x-1)}{x-1}=\frac{x+1}{x-1}\cdot c(p,x-1)+\frac{1}{p}$。
看起来没有什么优美的通项式。先退一步，根据之前的式子有 $g(p,u,v)=\frac{c(p,u-1)+\frac{u-1}{p}}{u(u-1)}$。我们需要对每个询问求 $\sum\limits_{p<u} g(p,u,v)\cdot a_p=\sum\limits_{p<u}\frac{c(p,u-1)\cdot a_p+\frac{u-1}{p}\cdot a_p}{u(u-1)}$。瓶颈在于求 $\sum\limits_{p<u} c(p,u-1)\cdot a_p$。
注意到如果按 $x$ 从小到大维护所有的 $c(p,x)\cdot a_p$，就形如全局乘、区间加固定数列（$\frac{a_i}{i}$）、全局和，所以可以把所有询问离线之后上一棵线段树维护。$O(n\log n)$。
其实 $p<u<v$ 的时候有 $g(p,u,v)=\frac{1}{p(p+1)}$，如果您知道如何通过非打表做法发现这个东西的话请踢我一下。
```cpp
const ll J=1e18,N=2e5+7,P=998244353;
ll qp(ll x,ll y=P-2) { return y?(y&1?x:1)*qp(x*x%P,y>>1)%P:1; }
ll n,q,fac,a[N],sp[N],ans[N];
vector<pll> qb[N];
struct que { ll u,v,p; } b[N];
ll cal(ll u,ll v) {
ll res=1;
for (ll i=u+1;i<=v;i++) res=((i+1)*qp(i-1)%P*res+qp(u))%P;
return res;
}
struct sgt {
ll t[N<<2],gt[N<<2],tg[N<<2];
sgt() { fill(gt,gt+(N<<2),1); }
void upm(ll p,ll z) { (t[p]*=z)%=P,(gt[p]*=z)%=P,(tg[p]*=z)%=P; }
void upa(ll p,ll l,ll r,ll z) { (t[p]+=(sp[r]+P-sp[l-1])*z)%=P,(tg[p]+=z)%=P; }
void pdn(ll p,ll l,ll r,ll mid) {
if (gt[p]!=1) upm(p<<1,gt[p]),upm(p<<1|1,gt[p]),gt[p]=1;
if (tg[p]) upa(p<<1,l,mid,tg[p]),upa(p<<1|1,mid+1,r,tg[p]),tg[p]=0;
}
void pup(ll p) { t[p]=(t[p<<1]+t[p<<1|1])%P; }
void add(ll x,ll y,ll z,ll p=1,ll l=1,ll r=n) {
if (x>y) return;
if (x<=l&&r<=y) return upa(p,l,r,z);
ll mid=l+r>>1; pdn(p,l,r,mid);
if (x<=mid) add(x,y,z,p<<1,l,mid);
if (y>mid) add(x,y,z,p<<1|1,mid+1,r);
pup(p);
}
} T;
void mian() {
scanf("%lld%lld",&n,&q),fac=1;
for (ll i=2;i<=n;i++) scanf("%lld",&a[i]),sp[i]=(sp[i-1]+a[i]*qp(i))%P,(fac*=i-1)%=P;
for (ll i=1,u,v;i<=q;i++) scanf("%lld%lld",&u,&v),qb[u].pb({v,i});
for (ll u=1;u<=n;u++) {
for (pll vv:qb[u]) { ll v=vv.fi;
ll ru=(sp[u-1]+a[u])%P,rv=(sp[v-1]+a[v])%P;
ll ruv=(T.t[1]*qp(u*(u-1)%P)+sp[u-1]*qp(u))%P;
ll uuv=qp(u)*a[u]%P;
ans[vv.se]=(ru+rv+P-(ruv+uuv)*2%P)*fac%P;
}
T.upm(1,(u+1)*qp(u-1)%P),T.add(1,u-1,1),T.add(u,u,u);
}
for (ll i=1;i<=q;i++) cout<<ans[i]<<"\n";
}
```