题解 UVA1205 【Color a Tree】

推广博客： https://llf0703.com/p/uva-1205.html 贪心策略和其他题解一样，选取最大的点和它的父节点合并。 只是我看其它题解每次找最大都是 $O(n)$ 把全部扫一遍，就想到用优先队列来优化。 不过问题也是显然的，每次合并我们都会删除当前点并改变父节点的值，但之前父节点肯定也已经放进了队列，而优先队列显然不能满足直接修改的条件。 但仔细一想，每次都是从权值最大节点合并上来，这就意味着**更新后的父节点的值一定大于原来的值**，所以在优先队列中，取到的一定是自己的最优解。然后我们再用一个 $vis[]$ 记录节点是否被取到过就可以防止重复的情况。 还有个细节是根节点不能被放进队列。因为过程中随时都有可能把根节点加入队列，所以每次都要判断一下。 ```cpp #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; } ```