题解：P9454 [ZSHOI-R1] 巡城

题目：

从 \(1\) 出发，求期望 dfn 序。

\(1\) 点很特殊，先固定 \(1\) 点，发现去除 \(1\) 后是森林，而 \(1\) 把他们都连起来了。

先固定一棵树的一个根 \(rt\)，思考这时 \(x\) 点的期望 dfn 序会被三种点贡献：

• \(rt→x\) 每个点贡献 \(1\)。
• \(x\) 子树内每个点贡献 \(0\)。
• 其他节点贡献 \(\frac{2}{1}\)。
  最后一个有点反直觉证一下：
  假设 \(v\) 为其他节点，\(x\) 与 \(v\) 相对顺序只有两种，手玩一下就知道了。

然后再固定一棵树的另外一个根