UVA1205 Color a Tree

· · 题解

Preface

题目链接

双倍经验

三倍经验

这是一道经典题。

Statement

有一个 n 个结点的树，根结点为 r。每个结点有一个权值 c_i，要求按一定顺序访问每个结点，规定必须先访问父亲结点以后才能访问子结点，设 u 在第 f_u 次被访问，要求 \sum_{i=1}^nc_i\cdot f_i 的最小值。

Solution

感性地理解可以发现 c_i 越大的越要先访问。证明即考虑 u,v 两个结点的顺序，如果先 u 再 v 就是 T\cdot c_u +(T+1)\cdot c_v，反之则是 T\cdot c_v+(T+1)\cdot c_u，移项易证。

考虑把这个思路推广到更多结点的情况，设有两个序列 A,B。可以把本来两个序列的基数干掉，剩下的就是比较 |A|\cdot \sum B 和 |B|\cdot \sum A，即 \frac{\sum A}{|A|} 和 \frac{\sum B}{|B|}，即平均数。

这样每次把最大的和父亲合并即可，时间复杂度 O(n^2)，可以 AC。但是，可以用 priority_queue + 并查集优化成 O(n\log n)，下面程序即优化版本。

Summary

经典 exchange arguments 题，溜。

Code

//AC!
#include<iostream>
#include<cstdio>
#include<queue>
//#define int long long
#define repe(i,l,r) for(int (i)=l;(i)<=r;(i)++)
#define rep(i,n) for(int (i)=1;(i)<=n;(i)++)
#define FOR(i,r,l) for(int (i)=r;(i)>=l;(i)--)
#define INF 0x3f3f3f
#define pii pair<int,int>
#define ll long long
#define mpr make_pair
#define pb push_back
#define F first
#define S second
#define sz(v) (int)((v).size())
#define ALL(v) (v).begin(),(v).end()
#define rsort(v) sort(ALL(v),greater<int>())
#define lb(v,x) (int)(lower_bound(ALL(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(ALL(v),x)-v.begin())
#define uni(v) v.resize(unique(ALL(v))-v.begin())
using namespace std;
int read(){int sum=0,f=1;char c;c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){sum=(sum<<1)+(sum<<3)+(c-'0');c=getchar();}return sum*f;}
void out(int x){if(x<0){x=-x;putchar('-');}if(x>=10)out(x/10);putchar(x%10+'0');}
void die(string s){cout<<s<<endl;exit(0);}
int fast(int a,int b,int P){int res=1;if(P<=0){while(b){if(b&1)res=res*a;a=a*a;b>>=1;}}else{while(b){if(b&1)res=res*a%P;a=a*a%P;b>>=1;}}return res;}
using namespace std;
const int N=1010;
int n,r,c[N],fa[N];
struct node{
    int sum,siz,fat;
}tree[N];
bool vis[N];
priority_queue<pair<double,int> > pq;
int getfa(int u){
    if(fa[u]==u)return u;
    return fa[u]=getfa(fa[u]);
}
int main(){
    while(1){
        n=read(),r=read();
        if(!n)break;
        int ans=0;
        for(int i=1;i<=n;i++){
            c[i]=read();
            fa[i]=i;
            tree[i].sum=c[i];
            tree[i].siz=1;
            ans+=c[i];
            vis[i]=0;
            if(i!=r)pq.push(mpr(1.0*c[i],i));
        }
        int u,v;
        for(int i=1;i<n;i++){
            u=read(),v=read();
            tree[v].fat=u;
        }
        while(!pq.empty()){
            u=pq.top().S;
            pq.pop();
            if(vis[u])continue;
            vis[u]=1;
            int rt=getfa(tree[u].fat);
            ans+=tree[rt].siz*tree[u].sum;
            tree[rt].sum+=tree[u].sum;
            tree[rt].siz+=tree[u].siz;
            fa[u]=rt;
            if(rt!=r){
                pq.push(mpr(1.0*tree[rt].sum/tree[rt].siz,rt));
            }
        }
        out(ans),putchar('\n');
    }
    return 0;
}