对于任意 $u>v$ 的点对 $(u,v)$，其对期望值的贡献如下：

• 若 $u$ 是 $v$ 的祖先，则贡献为 $1$。记这样的点对有 $A$ 组。
• 若 $v$ 是 $u$ 的祖先，则贡献为 $0$。记这样的点对有 $B$ 组。
• 否则，贡献为 $\frac{1}{2}$。记 $N=\frac{n(n-1)}{2}$，则这样的点对有 $N-A-B$ 组。

则答案为 $A+\frac{N-A-B}{2}=\frac{N+A-B}{2}$。

记 $f_i$ 为当节点 $i$ 为根时上式中 $A-B$ 的值。对于固定的 $i$，不难用树状数组在一趟 dfs 内求出 $f_i$，则求单个 $f_i$ 的复杂度为 $O(n \log n)$，总复杂度 $O(n^2 \log n)$。

考虑换根。当根节点从节点 $u$ 移到子节点 $v$ 时，不难发现：

• 减少的贡献为 $u$ 对 $v$ 的子树的贡献。记 $h_v$ 为 $v$ 的子树中编号比 $u$ 小的节点个数，则该部分贡献为 $-h_v+(\text{siz}_v-h_v)$。
• 增加的贡献为 $v$ 对 $v$ 的外子树的贡献。记 $g_v$ 为 $v$ 的子树中编号比 $v$ 小的节点个数，则该部分贡献为 $v-1-g_v-[n-\text{siz}_v-(v-1-g_v)]$。

综上，总转移方程为

$$f_v=f_u-2h_v-2g_v+2\text{siz}_v+2v-n-2$$

求 $h_v,g_v$ 即为求某段连续 dfn 区间内编号小于某个阈值的节点个数，这就是一个二维数点，可做到 $O(n \log n)$。dp 是 $O(n)$ 的，总复杂度 $O(n \log n)$。