【题解】给树染色

题目链接

解题思路

设最大点为b,其父节点为a,c为其他任意点
如果先染 $a,b$ ,再染 $c$ ,分值是 $a+2b+3c$ ;
如果先染 $c$ ,再染 $a,b$ ,分值是 $c+2a+3b$ ;
所以当 $a+2b+3c<c+2a+3b$ 时应该先染 $a,b$
即 $2c<a+b$ 。
将它推广到两组很多的点中,则
$a_1,a_2,...a_n$ 和 $b_1,b_2,...b_n$ 中
则应判断 $S_ab=\sum^n_{i=1}a_i*i+\sum^{n+m}_{i=n+1}b_i*i $和 $S_ba=\sum^m_{i=1}b_i*i+\sum^{n+m}_{i=m+1}a_i*i$ 的大小。
$S_ab-S_ba<0\rightarrow \frac{\sum^n_{i=1}a_i}{n}<\frac{\sum^m_{i=1}b_i}{m}$
即应先取平均数较大的一组。

我们用priority_queue来维护大小,并查集来记录合并情况即可。

如果大家理不通思路,可以看这篇题解

代码

#include<bits/stdc++.h>
using namespace std;
int n,R;
struct node{
    int father,sum,num;
}a[1005];
struct kkk{
    double ave;
    int pos;
};
struct cmp{
    bool operator() (kkk aa,kkk bb){
        return aa.ave<bb.ave;
    }
};
priority_queue<kkk,vector<kkk>,cmp> q;
int f[1005],vis[1005];//vis避免重复入队 
int find(int x){
    if(x==f[x])return x;
    return f[x]=find(f[x]);
}
long long ans;
int main(){
    cin>>n>>R;
    kkk now,nxtt;
    for(int i=1;i<=n;i++){
        vis[i]=0,f[i]=i;
    }
    for(int i=1;i<=n;i++){
        cin>>a[i].sum;
        ans+=a[i].sum;
        a[i].num=1;
        if(i!=R){
            now.ave=a[i].sum,now.pos=i;
            q.push(now);
        }
    }
    int u,v;
    for(int i=1;i<=n-1;i++){
        cin>>u>>v;
        a[v].father=u;
    }
    while(!q.empty()){
        now=q.top(),q.pop();
        if(vis[now.pos])continue;
        vis[now.pos]=1;
        int fnow=find(a[now.pos].father);
        ans+=a[fnow].num*a[now.pos].sum;//祖先节点的大小*当前节点的个数 
        a[fnow].sum+=a[now.pos].sum;
        a[fnow].num+=a[now.pos].num;
        if(fnow!=R){
            nxtt.ave=double(a[fnow].sium)/a[fnow].num;
            nxtt.pos=fnow;
            q.push(nxtt);
        }
        f[now.pos]=fnow;
    }
    cout<<ans<<endl;
    return 0;
} 

PS:写了一个早上这道题,看了好多篇题解,脑子昏昏沉沉的,下午还要上课。难受QAQ
祝大家写题顺利!

本文链接:http://kaispace.com.cn/index.php/archives/683/

如果未注明出处,复制公开后需将注明本博客链接。
打赏作者