原题链接:115.给树染色
解题思路
贪心+树上操作+并查集思想+模拟性质
首先这道题有一个错误的思想,那就是看当前节点的子节点,选择最大的那个节点,这个明显是错误的,如下图所示。
如果按照上面的错误贪心实现肯定是错误的。
下面是正确的贪心思路
我们知道,我们肯定是要权值val最大的点x,越先被染色越好,这是正确的贪心,那么我们如何染色呢?如果说我们要让x点染色的话,那么肯定它的父亲father[x]必须先被染色。既然如此的话,那么我们接着可以这样思考。
我们现在面临两个分支,如上图中的根节点1,到底选择2分支,还是3分支的时候。我们发现自然是选择2好,但是计算机不知道,那么如何让计算机知道了,我们可以设置一个数组w,设w[x]表示为x为根节点的树的平均权值,也就是w[x]=x子树的权值总和/x子树的个数。
样例代码
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int n,root;
struct Node
{
int p,s,v;
double avg;
}nodes[N];
int find()
{
double avg=0;
int res=-1;
for(int i=1;i<=n;i++)
if(i!=root&&nodes[i].avg>avg)
{
avg=nodes[i].avg;
res=i;
}
return res;
}
int main()
{
cin>>n>>root;
int ans=0;
for(int i=1;i<=n;i++)
{
cin>>nodes[i].v;
nodes[i].avg=nodes[i].v;
nodes[i].s=1;
ans+=nodes[i].v;
}
for(int i=0;i<n-1;i++)
{
int a,b;
cin>>a>>b;
nodes[b].p=a;
}
for (int i = 0; i < n - 1; i ++ )
{
int p = find();
int father = nodes[p].p;
ans += nodes[p].v * nodes[father].s;
nodes[p].avg = -1;
for (int j = 1; j <= n; j ++ )
if (nodes[j].p == p)
nodes[j].p = father;
nodes[father].v += nodes[p].v;
nodes[father].s += nodes[p].s;
nodes[father].avg = (double)nodes[father].v / nodes[father].s;
}
cout << ans << endl;
return 0;
}