题解：P12479 [集训队互测 2024] 长野原龙势流星群

· · 题解

做法其实和 UVA1205 Color a Tree 是一样的，可以在做完这题后看看这道。

思路

考虑按权值从大到小枚举点，每个点有三个值，分别是下标，大小和平均权值，假设前面的已经处理完，那么目前枚举的 i 就是最大的，那么 ans_i 就为这里的平均权值。注意到这个点只能对父亲造成贡献（题目要求只能选子树内的），由于我们是从大到小枚举，如果父亲没有被枚举，那么合并后父亲一定会更优，合并之后把这个新点扔进集合，下标仍是父亲那个点的下标，权值和大小更新一下就好了，然后删掉原来那个点，重复这个过程直到空，这样算出来的答案一定是最优的。

证明比较显然，首先对于点 i，如果它需要儿子 j 的一部分，那么选的一定的是以 j 为根的最平均权值大的连通块，然后就是合并顺序，由于 a > b > c，那么 a,c 的平均数大于 b,c 的平均数，所以对于 c 来讲只有可能是 a,c 和 a,b,c 中的一个，那么能选的话就一定会选 a，所以这个合并顺序就是最优的。

具体实现的话，使用并查集维护点权，然后删点的话我们没必要真的去删，注意到一个事实，每次合并答案一定更优，假设合并完平均权值没变也更优，这是因为由于值是从大到小枚举的，在保证值大的时候尽量保证个数多，这样一来小的影响就会降低。更优就会优先访问，那么记一个 vis 记录是否便利了即可。

关于值相同的情况，注意到题目特殊的建树方式，祖先下标一定小于自己，我们第二关键字为下标的话就可以完美解决这个问题了。

code

#include<bits/stdc++.h>
using namespace std;
namespace IO
{
    template<typename T>
    void read(T &_x){_x=0;int _f=1;char ch=getchar();while(!isdigit(ch)) _f=(ch=='-'?-1:_f),ch=getchar();while(isdigit(ch)) _x=_x*10+(ch^48),ch=getchar();_x*=_f;}
    template<typename T,typename... Args>
    void read(T &_x,Args&...others){Read(_x);Read(others...);}
    const int BUF=20000000;char buf[BUF],top,stk[32];int plen;
    #define pc(x) buf[plen++]=x
    #define flush(); fwrite(buf,1,plen,stdout),plen=0;
    template<typename T>inline void print(T x){if(!x){pc(48);return;}if(x<0) x=-x,pc('-');for(;x;x/=10) stk[++top]=48+x%10;while(top) pc(stk[top--]);}
}
using namespace IO;
const int N = 2e5+10;
int n,fa[N],f[N],v[N],y,z;
priority_queue<pair<double,int> >p;
double ans[N],w[N],siz[N],x;
int find(int x)
{
    if(f[x] == x) return x;
    return f[x] = find(f[x]);
}
signed main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    read(n);
    for(int i = 2;i <= n;i++) read(fa[i]);
    for(int i = 1;i <= n;i++) cin >> w[i],f[i] = i,siz[i] = 1;
    for(int i = 1;i <= n;i++) p.push(make_pair(w[i],i));
    while(!p.empty())
    {
        x = p.top().first,y = p.top().second; p.pop();
        if(v[y]) continue; v[y] = 1;
    //  cout<<x<<" && "<<y<<" "<<siz[y]+siz[find(fa[y])]<<" "<<w[find(fa[y])]*siz[find(fa[y])]+x<<" "<<w[y]<<" "<<siz[]<<endl;
        ans[y] = x;
        if(!fa[y]) continue;
        if(!v[find(fa[y])]) w[find(fa[y])] = 1.0*(w[find(fa[y])]*siz[find(fa[y])]+x*siz[y])/(siz[y]+siz[find(fa[y])]),p.push(make_pair(w[find(fa[y])],find(fa[y])));
    //  cout<<x<<" %% "<<y<<" "<<find(fa[y])<<" "<<w[find(fa[y])]<<endl;
        siz[find(fa[y])] += siz[y],f[y] = find(fa[y]);
    }
    for(int i = 1;i <= n;i++) printf("%.7f\n",ans[i]);
    return 0;
}