题解

思路推导

树上从城市 $1$ 出发且不访问已到过城市时，除起点外唯一的已访问邻点就是父亲。因此在一个非叶城市，下一步会等概率选择它的所有儿子。

可以把到达某个城市的概率沿树向下传播。若到达城市 $u$ 的概率为 $p$，它有 $c$ 个儿子，则每个儿子的到达概率都是 $p/c$。旅行最终停在以城市 $1$ 为根的叶子，某个叶子对期望的贡献等于“到达它的概率乘以它的深度”。

做法

从城市 $1$ 建立父子关系，记录每个城市的深度和到达概率。按遍历顺序处理城市：若它没有儿子，就把“概率乘深度”加入答案；否则把当前概率平均分配给所有儿子。

实现中使用显式栈或队列建立父子关系，避免深链递归带来的栈空间风险。

正确性证明

对根到任意城市的深度归纳。根的到达概率为 $1$。若城市 $u$ 的记录概率等于旅行到达它的真实概率，那么条件于到达 $u$，马在它的 $c$ 个未访问儿子中均匀选择，故每个儿子的真实到达概率均为 $p_u/c$，与算法传播值一致。由归纳，所有城市的概率均正确。

旅行只会在根树叶停止，各叶子事件互斥且覆盖全部可能过程。算法按定义累加每个叶子的停止概率与路程长度之积，因此所得和正是旅行长度的期望。

复杂度分析

每个城市和每条道路只处理常数次，时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。