长野原龙势流星群 题解

· · 题解

简单题。

考虑点权最大的一个节点，假设其为 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;
}