主页
搜索
最近更新
数据统计
申请密钥
批量保存
开发版网站（新前端）
系统公告
1
/
1
请查看完所有公告
题解：CF1777D Score of a Tree
最后更新于 2025-08-28 08:56:36
作者
2huk
分类
题解
题解
CF1777D
复制 Markdown
查看原文
转到新前端
删除文章
更新内容
upd：原来的代码锅了。 考虑转化成一个概率论的问题，即每个点的权 $01$ 随机，求期望点权和。这个东西再乘 $2^n$ 即答案。 显然节点 $u$ 在时刻 $t$ 时的值，是**初始所有（$u$ 子树内）距离 $u$ 为 $t$ 的点的点权异或和**。这里若 $u$ 子树内没有距离为 $t$ 的点则 $u$ 点权必为 $0$。而当这种情况发生及之后其贡献都为 $0$，也就不需要考虑了。令这种情况发生时 $t = f(u)$。不难发现 $f(u) = \max_{v \in \operatorname{son}_u}f(v)+1$。 因为所有点都是完全随机，所以我们并不注重距离 $u$ 为 $t$ 的点具体是哪些，而只需要注重**数量**。 即，令 $u$ 子树内距离 $u$ 为 $t$ 的点的数量为 $k$。[可以证明](https://www.luogu.com.cn/paste/cq094d2m)这 $k$ 个点里有奇数个点的初值为 $1$ 的概率为 $\frac 12$，即其异或和为 $1$ 的概率为 $\frac 12$。 所以这个东西和 $t$ 也无关了。也就是说，只要 $t \le f(u)$ 则点 $u$ 的期望点权为 $\frac 12$。否则期望为 $0$。 所以答案为： $$ \sum\left( \dfrac 12 f(i)+0 \times (10^{100}-f(i))\right)=\dfrac 12 \sum f(i) $$ 别忘了再乘上 $2^n$。真正答案为 $2^{n-1}\sum f(i)$。 代码：<https://codeforces.com/contest/1777/submission/289078704>
正在渲染内容...
点赞
5
收藏
0
