这是本文档旧的修订版！
Codeforces Round #706 (Div. 1)
B. Tree Array
题意
给定 $n$ 个点的树，点编号分别为 $1\sim n$。
初始时等概率随机选择一个点，接下来每次操作从未选择的且与已经选择的点相连的点中等概率随机选择一个点。
根据选择的顺序可以得到由点的编号构成的序列，问序列逆序对的期望个数。
题解
首先枚举初始选择点，并将初始选择点作为根节点。
不难发现，每个节点只有在所以祖先结点被选取后才有机会选取。
同时对任意点对 $(u,v)$，当 $p=\text{LCA}(u,v)$ 被选取后，他们的其余祖先节点被选取的概率总是相等的。
于是不妨设 $u\gt v,d_1=d_u-d_p,d_2=d_v-d_p$，于是 $(u,v)$ 构成逆序对的概率等价于如下模型：
两个袋子中分别有 $d_1,d_2$ 个球，每次有 $t$ 概率从某个袋子中选一个球，也有 $1-2t$ 概率无事发生，问 $d_2$ 个球的袋子先被取空的概率。
不难发现 $\text{dp}(d_1,d_2)=\cfrac {\text{dp}(d_1-1,d_2)+\text{dp}(d_1,d_2-1)}2$。然后暴力统计固定根每个点对贡献即可，时间复杂度 $O(n^3)$。
C. Converging Array
题意
一开始有 $a[1\sim n],b[1\sim n-1]$，接下来有无限次操作。
每次操作随机选择一个 $1\le i\le n-1$， $a_i=\min\left(a_i,\cfrac {a_i+a_{i+1}-b_i}2\right),a_{i+1}=\max\left(a_i,\cfrac {a_i+a_{i+1}+b_i}2\right)$。
可以证明无限次操作后序列 $a[1\sim n]$ 收敛于固定值。
每次询问给定 $x$，问有多少序列 $a[1\sim n]$ 满足：
- $0\le a_i\le c_i$
- 最终收敛后 $a_1\ge x$
题解
设最终得到序列为 $f[1\sim n]$。观察发现，每次操作不改变 $\sum a_i$，且最后有 $f_{i+1}-f_i\ge b_i$。
设 $sa_i=\sum_{j=1}^i a_j,sb_1=0,sb_{i+1}=\sum_{k=1}^j b_k,ssb_i=\sum_{j=1}^i sb_i,sc_i=\sum_{j=1}^i c_j$。
不难发现最后形式为 $f_1+sb_1,f_1+sb_2,f_1+sb_3 \cdots f_1+sb_k,f_{k+1}\cdots$，其中 $f_t\gt f_1+sb_t(t\gt k)$。
同时有 $\sum_{i=1}^k f_i+sb_i=\sum_{i=1}^k a_i$，且 $\sum_{i=1}^t f_i+sb_i=\sum_{i=1}^t a_i\ge \sum_{i=1}^t a_i(t\neq k)$。
于是有 $f_1=\min_{i=1}^n\left(\cfrac {sa_i-ssb_i}i\right)$。枚举询问的 $x$，对每个 $x$，保证 $\cfrac {sa_i-ssb_i}i\ge x$ 即可计算答案个数。
设 $\text{dp}(i,s)$ 表示 $\sum_{j=1}^i a_i=s$ 的情况，$m=\max c_i$，利用差分可以 $O(n^2m)$ 计算答案。
最后有 $\min\left(\cfrac {-ssb_i}i\right)\le f_1\le \min\left(\cfrac {sc_i-ssb_i}i\right)$，于是有 $\max(f_1)-\min f_1\le m$。
即有效的 $x$ 只有 $O(m)$ 个，最终时间复杂度 $O\left(n^2m^2\right)$。
