题意分析
发现平均值不好维护，因此可以维护连通块的大小与权值和。
假设得到了以 $x$ 为根的连通块的答案，那么如果存在一个连通块包含了这个连通块，一定要包含 $x$ 的父节点。因此在得出 $x$ 的答案后，$x$ 连通块的作用等价于其父节点 $\textit{father}_x$ 与 $x$ 的连通块构成的大连通块。
因此考虑一种数据结构，能够维护这种操作，考虑带权并查集维护连通块大小、权值和。
同时使用大根堆每次找平均值最大的连通块，并更新其父节点的连通块信息即可。初始时所有连通块均只有一个节点。而点权最大的的对应连通块显然是自己。
这些连通块维护的答案一定是不劣的，否则由于大根堆，已经维护过了更优的答案。
时间复杂度 $\mathcal O(n\log n)$。
AC 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
typedef long long ll;
constexpr const double eps=1e-8;
constexpr const int N=5e5;
int n,a[N+1],father[N+1];
double ans[N+1];
bool vis[N+1];
struct node{
int x;
ll value;
int size;
};
bool operator <(node a,node b){
__int128 valueA=(__int128)a.value*b.size,valueB=(__int128)b.value*a.size;
if(valueA!=valueB){
return valueA<valueB;
}else{
return a.x<b.x;
}
}
struct dsu{
int f[N+1],size[N+1];
ll value[N+1];
int find(int x){
if(f[x]==x){
return x;
}else{
return f[x]=find(f[x]);
}
}
void build(int n){
for(int i=1;i<=n;i++){
f[i]=i;
value[i]=a[i];
size[i]=1;
}
}
void merge(int x,int y){
x=find(x),y=find(y);
f[x]=y;
size[y]+=size[x];
value[y]+=value[x];
}
}t;
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n;
for(int i=2;i<=n;i++){
cin>>father[i];
}
priority_queue<node>q;
for(int i=1;i<=n;i++){
cin>>a[i];
q.push({i,a[i],1});
}
t.build(n);
while(q.size()){
node top=q.top();q.pop();
int &x=top.x;
if(x!=t.find(x)){
continue;
}
if(1.0*t.value[x]/t.size[x]>=ans[x]){
ans[x]=1.0*t.value[x]/t.size[x];
if(father[x]){
father[x]=t.find(father[x]);
t.merge(x,father[x]);
q.push({father[x],t.value[father[x]],t.size[father[x]]});
}
}
}
for(int i=1;i<=n;i++){
cout<<fixed<<setprecision(9)<<ans[i]<<'\n';
}
cout.flush();
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
