UVA1205 Color a Tree

洛谷博客： https://www.luogu.org/blog/llf/solution-uva1205

贪心策略和其他题解一样，选取最大的点和它的父节点合并。

只是我看其它题解每次找最大都是 $O(n)$ 把全部扫一遍，就想到用优先队列来优化。

不过问题也是显然的，每次合并我们都会删除当前点并改变父节点的值，但之前父节点肯定也已经放进了队列，而优先队列显然不能满足直接修改的条件。

但仔细一想，每次都是从权值最大节点合并上来，这就意味着更新后的父节点的值一定大于原来的值，所以在优先队列中，取到的一定是自己的最优解。然后我们再用一个 $vis[]$ 记录节点是否被取到过就可以防止重复的情况。

还有个细节是根节点不能被放进队列。因为过程中随时都有可能把根节点加入队列，所以每次都要判断一下。

#include<bits/stdc++.h>
#define pr pair<double,int>
#define mp make_pair

using namespace std;

inline int read()
{
    char ch=getchar();
    int f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

struct pt{
    int t;
    double w;
} s[1005];
int head[1005],cnt,n,m,a,b,root,v[1005],fa[1005];
bool vis[1005];

inline void init()
{
    cnt=0;
    memset(vis,0,sizeof(vis));
    memset(fa,0,sizeof(fa));
}

int main()
{
    while (~scanf("%d%d",&n,&root) && n && root)
    {
        init();
        priority_queue <pr> q;
        int ans=0;
        for (int i=1;i<=n;i++) 
        {
            v[i]=read();
            s[i].w=v[i]*1.0;
            s[i].t=1;
            ans+=v[i];
            if (i==root) continue; //除根节点
            q.push(mp(s[i].w,i));
        }
        for (int i=1;i<n;i++)
        {
            a=read(); b=read();
            fa[b]=a;
        }
        for (int i=1;i<n;i++)
        {
            int x=q.top().second; q.pop();
            while (vis[x] || x==root) //一直取直到不重复也不是根
            {
                x=q.top().second;
                q.pop();
            }
            vis[x]=1; //记录已取过
            ans+=v[x]*s[fa[x]].t;
            for (int j=1;j<=n;j++)
                if (fa[j]==x)
                    fa[j]=fa[x];
            s[fa[x]].t+=s[x].t;
            v[fa[x]]+=v[x];
            s[fa[x]].w=1.0*v[fa[x]]/s[fa[x]].t;
            q.push(mp(s[fa[x]].w,fa[x])); //将更新后的父节点入队
        }
        printf("%d\n",ans);
    }
    return 0;
}