题目描述

难度分:$1700$

有一棵$n$个节点的树。节点编号从$1$到$n$。节点$1$是根节点。

输入$n(1≤n \leq 10^5)$和$p[2],p[3],…p[n]$，其中$p[i]$表示节点$i$的父节点$(1 \leq p[i] \lt i)$。

定义$start[i]$为访问到节点$i$时的时间戳，具体计算方式如下：

• 初始化$time=0$，从节点$1$出发，DFS这棵树。
• 每递归到一个新的节点$i$，先把$time$加一，然后记录$start[i]=time$。

在DFS之前，随机打乱每个节点的子节点列表。

对于每个节点$i$，输出$start[i]$的期望值。

与答案的误差不能超过$10^{-6}$。

输入样例$1$

7
1 2 1 1 4 4

输出样例$1$

1.0 4.0 5.0 3.5 4.5 5.0 5.0 

输入样例$2$

12
1 1 2 2 4 4 3 3 1 10 8

输出样例$2$

1.0 5.0 5.5 6.5 7.5 8.0 8.0 7.0 7.5 6.5 7.5 8.0 

算法

数学

这个题感觉还是比较难的，最重要的就是不要上来就看全局，从局部分析的话会更加清楚一点。

我们可以观察第一个样例，$1$有$2$、$3$、$4$三个孩子。以节点$3$为例，如果访问完$1$之后马上访问$3$，那么就是在$time=2$时访问$3$；如果访问完$2$之后再访问$3$，那就是在$time=cnt[2]+2$时访问$3$。在$2,3,4$的所有$6$个排列中，有$0.5$的概率$2$在$3$的左边，也有$0.5$的概率$4$在$3$的左边，所以得到$E_3=2+0.5cnt[2]+0.5cnt[4]$，而$cnt[2]+cnt[4]=n-1-cnt[3]$，所以$E_3=\frac{n-cnt[3]+3}{2}$。

再分析几个节点就可以发现$E_i=\frac{n-cnt[i]+depth[i]+1}{2}$，其中$depth[i]$是节点$i$的深度（深度从$1$开始），$cnt[i]$是以$i$为根节点的子树中有多少个节点。

复杂度分析

时间复杂度

DFS遍历整棵树一遍，计算出$cnt$数组和$depth$数组，时间复杂度为$O(n)$。然后遍历$i \in [1,n]$，对每个节点$O(1)$计算期望，时间复杂度为$O(n)$。因此，整个算法的时间复杂度也是$O(n)$。

空间复杂度

空间的消耗主要体现在三个方面：一是$cnt$数组和$depth$数组的消耗，它们都是$O(n)$规模的；二是无向树的邻接表消耗，节点数量是$O(n)$规模，边的数量也是$O(n)$规模，因此整体还是$O(n)$的；三是DFS带来的空间开销，在最差的情况下也要递归$n$层，因此空间开销也是$O(n)$的。整个算法的额外空间复杂度为$O(n)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;
const int N = 100010;
int n, p[N], cnt[N], depth[N];
vector<int> graph[N];

void dfs(int u, int d) {
    cnt[u] = 1;
    depth[u] = d;
    for(int v: graph[u]) {
        dfs(v, d + 1);
        cnt[u] += cnt[v];
    }
}

int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        graph[i].clear();
    }
    for(int i = 2; i <= n; i++) {
        scanf("%d", &p[i]);
        graph[p[i]].push_back(i);
    }
    dfs(1, 1);
    for(int i = 1; i <= n; i++) {
        printf("%.8lf ", (n - cnt[i] + depth[i] + 1) / 2.0);
    }
    return 0;
}