显然到最远的宝藏的距离最小的点是宝藏的直径中点，可能有两个最小的，那直径中点就是它们之间的边的中点。设直径为 $2d$，那么以直径中点为根，深度小于 $d$ 的点概率是 $1/2$，深度大于 $d$ 的点的概率是 $0$。深度等于 $d$ 的点的概率比较复杂，但容易发现一定大于 $1/2$，且所在的根的子树深度等于 $d$ 的点越多，概率越小。时间复杂度 $O(n)$。
QOJ.ac
QOJ
As we are currently experiencing an overwhelming number of web requests for fetching user submissions, we have temporarily disabled the full submissions list. You must now be logged in to view submissions.
Discussion #315 for Problem #1652. One Piece
Type: Editorial
Status: Open
Posted by: jiangly
Posted at: 2025-12-14 07:03:09
Last updated: 2025-12-14 07:03:12
题解
Comments
No comments yet.