被 hack 的缺陷做法

我們考慮任意一個節點 \(i\) 如果已經是當前平均數最大值，那么必然不存在一個節點能夠使節點 \(i\) 的平均數更大。考慮到節點 \(i\) 的父節點 \(j\) ，此時節點 \(j\) 的平均值一定 \(\le\) 節點 \(i\) 的平均值，所以此時可以通過節點 \(i\) 的平均值更新節點 \(j\) 的平均值，于是我們可以考慮使用優先隊列維護最大值。

然后考慮題目中要求求的值是：

每個點 \(u\) 找到一個以 \(u\) 為根的非空連通塊并最大化這個連通塊內所有點的點權的平均值

所以此時的節點 \(i\) 在更新了父節點 \(j\) 后，就無法直接更新其它節點了（因為節點 \(i\) 并不能更新它的子節點），而是通過更新后的父節點 \(j\) 來間接更新其它節點，于是我們考慮用并查集維護連通塊，在每次節點 \(i\) 在更新了父節點 \(j\) 后就將節點 \(i\) 并入節點 \(j\) 所在的連通塊。

但值得注意的是，節點 \(i\) 在完成了更新節點 \(j\) 后，其部分不優的值可能仍然在優先隊列中，所以每次查詢優先隊列最大值后還要判斷這個最大節點 \(i\) 是否是自己所處連通塊的根，如果是，則可以更新父節點 \(j\),否則跳過這個值。但以上的做法仍存在缺陷，于是我們不妨觀察一下 hack 數據。

優化缺陷部分

考慮到 Subtask # 5 中的 hack 數據：

輸入
4
1 2 2
1 2 4 3
輸出
2.5000000000
3.0000000000
4.0000000000
3.0000000000

如果一個節點的平均值是 \(\frac{q}{p}\) 另一個節點的平均值是 \(\frac{s}{t}\)，我們會令其中更大的值先被用于更新，但如果有 \(\frac{q}{p} = \frac{s}{t}\),我們應該認為 \(p\) 與 \(t\) 更大的一個更優，我們可以感性理解一下，當分母更大時，那么加上另外一個值時對于這個平均值的影響更小。

CODE

#include<bits/stdc++.h>
using namespace std;
int n,fa[200005],f[200005],w[200005];
struct node{
	long long x;
	int y,id;
}tr[200005];
bool operator <(node x,node y){
	return (__int128(x.x*y.y)==__int128(y.x*x.y))?x.y<y.y:(x.x*y.y)<__int128(y.x*x.y);
}
priority_queue<node> q;
int getf(int x){
	return (f[x]==x)?x:f[x]=getf(f[x]);
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=2;i<=n;i++)
		cin>>fa[i];
	for(int i=1;i<=n;i++){
		cin>>w[i];
		tr[i]={w[i],1,i};
		q.push(tr[i]);
		f[i]=i;
	}
	while(!q.empty()){
		node t=q.top();
		q.pop();
		if(f[t.id]!=t.id)
			continue;
		int k=getf(fa[t.id]);
		tr[k].x+=t.x;
		tr[k].y+=t.y;
		f[t.id]=k;
		if(k)
			q.push(tr[k]);
	}
	for(int i=1;i<=n;i++)
		cout<<setprecision(12)<<(long double)(1.0*tr[i].x/tr[i].y)<<endl;//setprecision(12)是保留12位小數，減小相對誤差
	return 0;
}