思路

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

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

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

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

时间复杂度：$O(n)$

代码

C++

#include <bits/stdc++.h>
using namespace std;

const int N = 100010;
vector<int> g[N];
int n;

long long ans = 0;

int dfs(int u, int fa) {
    int res = 0;
    int sum = 0;
    for (int v: g[u]) {
        if (v == fa) continue;
        int c = dfs(v, u);
        res = max(res, c);
        sum += c;
    }

    res = max(res, n - 1 - sum);
    ans += res;
    return sum + 1;
}

int main()
{
    scanf("%d", &n);

    for (int i = 1; i < n; ++i) {
        int u, v;
        scanf("%d%d", &u, &v);
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }

    dfs(1, 0);

    printf("%.10lf\n", 1.0 * ans / n);

    return 0;
}

java

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    static List<List<Integer>> tree = new ArrayList<>();
    static long res = 0;
    static int[] visited;
    static int n;

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        for (int i = 0; i < n + 1; i++) {tree.add(new ArrayList<>());}
        for (int i = 0; i < n - 1; i++) {
            int u = sc.nextInt();int v = sc.nextInt();
            tree.get(u).add(v); tree.get(v).add(u);}
        visited = new int[n+1];

        DFS(1);

        System.out.println(res/(double)n);

    }

    private static int DFS(int i) {
        int sum=0,max=0;
        visited[i]=1;
        for(int son:tree.get(i)){
            if(visited[son]==0){
                int sonNode = DFS(son);
                sum+=sonNode;
                max = Math.max(max,sonNode);
            }
        }
        res+=Math.max(max,n-sum-1);
        return sum+1;
    }
}

python

n = int(input())
edges = []
for i in range(n - 1):
    edges.append(list(map(int, input().split())))
#print(edges)
from collections import *
ma = defaultdict(list)
for u,v in edges:
    ma[u].append(v)
    ma[v].append(u)

ans = 0
def dfs(u, fa):
    global ans
    res = 0
    _sum = 0
    for v in ma[u]:
        if v == fa:
            continue
        c = dfs(v, u)
        res = max(res, c)
        _sum += c

    res = max(res, n - 1 - _sum)
    ans += res
    #print(ans, res)
    return _sum + 1

if n == 1:
    print("0.00000005")
    exit(0)

dfs(1, 0)
print("{:.10f}".format(ans / n))

题目描述

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

输入描述

第一行输入一个正整数$n$，代表树的节点数量 接下来的$n-1$行，每行输入两个正整数$u,v$，代表节点$u$和节点$v$有一条边连接。

$1\le n\le 10^5$

$1\le u,v\le n$

输出描述

一个浮点数，代表最终最大连通块的大小期望。如果你的答案和标准答案的相对误差小于$10^{-6}$，则认为你的答案正确。

样例1

输入

2
1 2

输出

1.000000000

说明

无论删除的是哪个节点，形成的森林的最大连通块大小均是 1.

样例2

输入

3
1 3
2 3

输出

1.6666666666667

说明

删除1号节点时，最大连通块大小为2。
删除2号节点时，最大连通块大小为1。
删除3号节点时，最大连通块大小为2。
因此随机选一个节点删除，连通块的大小期望是5/3