题目描述
难度分:$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;
}