题目描述

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

输入描述

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

思路

DFS 每个点 u ，当删除点 u 时，形成若干个子树 v1, v2, v3, 以及一个 u 的祖先连通块

v1，v2 和 v3 等子树的大小可以通过 DFS 获得，u 的祖先连通块大小为 n - 1 - (v1 + v2 + v3 + ...)

取所有子树以及 u 的祖先连通块大小的最大值即可

最终对于每个点删除后的最大连通块的大小累加，最后除以 n 即为期望。