2024.03.31-第3题-树的期望 - Problem Detail - CodeFun2000

ID: 882

Type: Default

1000ms

256MiB

Difficulty: 6

Uploaded By:

Tags>

字节跳动

题目描述

众所周知，点分治算法最重要的一个步骤是寻找一棵树的重心后删除，满足形成的森林中最大连通块尽可能小。但很可惜，塔子哥不会寻找树的重心，因此她会随机选择一个节点进行删除。这样就会导致最终算法的复杂度增加。塔子哥想知道，对于一个给定的树，随机取一个点删除，形成的森林中最大连通块大小的期望是多少?

输入描述

第一行输入一个正整数 $n$ ，代表树的节点数量