自动搬运

查看原文

来自洛谷，原作者为

	E_firework 重逢的时间短暂 所以一定毫无保留 用尽无声的电波 嘶吼

搬运于2025-08-24 23:15:52，当前版本为作者最后更新于2025-05-27 08:32:41，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

简单题。

考虑点权最大的一个节点，假设其为 $x$，那么以 $x$ 为根的答案一定是只选 $x$ 这一个点，因为在连通块中加入其他的节点不能使得答案变得更优。再考虑 $x$ 的父亲，假设其为 $y$。不难发现，如果一个最优的连通块包含了节点 $y$，那也一定会包含节点 $x$，因为加入节点 $x$ 一定不会使得答案变劣。那么我们可以直接把 $x$ 和 $y$ 缩成一个点处理。接下来只需要把找到点权最大的一个节点改为找到平均点权最大的一个节点，重复上述的过程就能得到每个节点的答案。使用优先队列+并查集可以很容易地维护上述过程，时间复杂度为 $O(n\log n)$。

code：

#include <bits/stdc++.h>
#define LL long long
#define Maxn 200005
using namespace std;
inline LL read(){char c;c = getchar();while(!(('0' <= c && c <= '9') || c == '-')) c = getchar();bool flag = 0;if(c == '-'){flag = 1;c = getchar();}LL tot = 0;while('0' <= c && c <= '9'){tot = 10 * tot + c - '0';c = getchar();}return flag ? -tot : tot;}
int fa[Maxn], f[Maxn], c[Maxn];
LL s[Maxn];
double ans[Maxn];
int find(int i){
    return i == f[i] ? i : f[i] = find(f[i]);
}
__int128 t1 = 1;
struct node{
    LL a;
    int b, id;
    bool operator<(const node i)const{
        return t1 * a * i.b < t1 * i.a * b;
    }
};
priority_queue<node> q;
int main(){
    int n = read();
    for(int i = 2; i <= n; i++) fa[i] = read();
    for(int i = 1; i <= n; i++) s[i] = read();
    for(int i = 1; i <= n; i++){
        f[i] = i, c[i] = 1;
        q.push({s[i], 1, i});
    }
    int x, y;
    while(q.size()){
        x = q.top().id;
        q.pop();
        if(f[x] != x) continue;
        ans[x] = 1.0 * s[x] / c[x];
        y = find(fa[x]);
        f[x] = y;
        if(y){
            s[y] += s[x];
            c[y] += c[x];
            q.push({s[y], c[y], y});
        }
    }
    for(int i = 1; i <= n; i++) printf("%.12lf\n", ans[i]);
    return 0;
}