题面有一棵nnn个节点的树每次操作会在还存在的节点中随机等概率地选一个点将以这个点为根的子树全部删去。问要把这棵树删光总操作次数的期望值是多少。思路将对每个节点进行的操作次数的期望值单独计算后再求和。什么是对每个节点的操作次数的期望值这里指的是直接选中它删掉以它为根的子树的次数的期望。为什么可以单独计算选到每个点的次数的期望值再合并用到了期望值的线性性质我不太清楚中文是不是这个就是对于很多次操作的期望值多次操作得到的值之和的期望值等于每次操作的期望值之和E(X1X2X3⋯Xn)E(X1)E(X2)⋯E(Xn)E(X_1X_2X_3\dots X_n)E(X_1)E(X_2)\dots E(X_n)E(X1​X2​X3​⋯Xn​)E(X1​)E(X2​)⋯E(Xn​)。可以直观地理解举个例子有一个骰子连续扔333次333次扔出来的总和的期望值是不是就等于333次每次扔出数值的期望值的和但是这个性质还有一个很有用的地方就是事件之间可以不独立。如何计算每个点操作次数的期望考虑点iii有一些情况会使你还没有对它操作它就完了那就是选择了它的祖先操作共有depi−1dep_i-1depi​−1个祖先记 root 的深度是 1此时对点iii的操作数是000。只有刚好选到了iii的时候对iii的操作数是111。其他的点选没选到无所谓因为不会删掉iii后面反正会删到iii所以对iii的操作次数无影响。得出结论期望值就是depi−1depi×01depi×11depi\frac{dep_i-1}{dep_i}\times0\frac{1}{dep_i}\times1\frac{1}{dep_i}depi​depi​−1​×0depi​1​×1depi​1​。代码结论和实现都异常地简单。#includebits/stdc.husingnamespacestd;intn,a,b,dep[100005];vectorintgo[100005];doubleans;voiddfs(intps,intfa){dep[ps]dep[fa]1;for(autog:go[ps])if(g!fa)dfs(g,ps);}intmain(){cinn;for(inti1;in;i){cinab;go[a].push_back(b);go[b].push_back(a);}dfs(1,0);for(inti1;in;i)ans1.0/dep[i];coutfixedsetprecision(10)ansendl;return0;}我当时看 CF 上的官方题解好像没有解释每个点的期望是怎么算的也可能只是我思路比较迟缓理解困难然后想了一会儿终于懂了遂记录了一下我成功说服我自己的过程希望大家听懂了感谢观看。