CF1777D

过了 t 个单位时间后，节点 $u$ 的值是什么？

是所有距离它为 $t$ 的节点的异或和。

F(A) 是树的和。

$\mathbb{E}(F(A))$ 是树的和的期望。

$2^n$ 种情况的总和 = 期望值 ✖️ $2^n$

那么怎么算 $\mathbb{E}(F(A))$ 呢？树的节点和的期望，等于节点期望的和，考虑每个节点。

对于节点 $u$ 在时间 $t$，它的期望 $\mathbb{E}(F_u(A))$ 可以通过距离它最远的节点距离来判断。

设距离节点 $u$ 最远的节点距离为 $d_u$

如果 $t \le d_{u}$，那么它的期望就是 $\frac{1}{2}$。

根据异或和的性质，在序列长度大于等于 1 时，异或和的期望始终由最后一位的概率决定，所以期望始终为 $\frac{1}{2}$。

所以在所有时间 $0 \le t \le 10^{100}$，只有 $0 \le t \le d_u$ 的期望是 $\frac{1}{2}$，剩下的期望全都是 0.

那么 $ans_u = (d_{u}+1) \times \frac{1}{2}$

知道了单个节点的期望，求出整个树的期望和后✖️$2^n$ 就是答案。

$Answer = \sum_{u=1}^{n}\frac{d_{u}+1}{2}$