对于官方题解做一点补充，对于一条长度为 n + 1 的链而言，假设从左到右节点编号为 1,\cdots,n + 1 ，此时记 dp_u 为从 u 开始，能够获胜的概率，显然我们有：
dp_u = \frac{1}{2}(dp_{u - 1} + dp_{u + 1})
这可以导出，dp 数组是一个等差数列，因此配合 dp_1 = 1, dp_{n+1} = 0 ，容易得到：
dp_u = \frac{n + 1 - u}{n}
换言之，如果仅仅考虑 fa = u - 1 与 u 的关系，我们得到：
dp_u = dp_{fa} \times \frac{x}{x + 1}\quad x = n + 1 - u
这里 x 为 u 到其子树中最近的叶子的距离，按照这个思路来思考，我们也很自然地得到了从链推广到树的递推式。
submission