学步园

原题 http://poj.org/problem?id=2054

题目大意：给你一棵树及每个点的权值和根，你需要把这颗树染色，每个时间只能染一个点（染一个点必须先染他的父亲），所需的花费是当前染色时间*这个点的权值，求最少花费（根必须第一个染），n<=1000  都组数据

这题初看时以为是tree dp ，但没有想出来，还是看了题解，发现是贪心，但是讲的都不明觉厉，只好拿着代码自己想了。。。。

这个题的大体思路就是最大一个要最先选，但是选它必须要选它父亲。于是我们就可以找到一个点X它的V[X]/num[X]是整棵树中最大的（用过的不算，root也不算），num[X]代表X号点所在的点是由几个点合并而成的，至于为什么是V[X]/num[X]，就是求一个v[X]的平均值。设Y是他的父亲，那么就可以把X与Y合并成Y（合并之后X的儿子的父亲就是Y了），我们记V[i]表示i号点的权值，一个点的的花费就是从它祖先的num之和*它的权值，那么在合并X、Y时，就把ans加上num[Y]*V[X]，然后把V[Y]增加V[X]就可以把以后祖先的num*v[X]也算进去了，当然num[Y]也要加上num[X]，因为X的儿子的父亲从X变成了Y。如此合并
n-1次后，就只剩一个跟节点了，这时再把ans加上V[root]就行了（第一个要染的点事root，所以每个点的染色时间都要+1，ans就应该加上给你的权值的和）

这题裸的是O(n^2)虽说可以过，不过可以用堆+并查集思想优化到(nlogn)

#include<queue>
#include<cstdio>
#include<cstring>
const int maxn=1010;
using namespace std;
struct zy{
	int num,W,T;
	zy(){}
	zy(int _num,int _W,int _T):num(_num),W(_W),T(_T){
	}
	bool operator <(const zy &a) const {
		return W*a.T<a.W*T;
	}
};
inline int getint(){
    char ch=getchar(); int tmp=0;
    while (ch<'0' || ch>'9') ch=getchar();
    for (;ch<='9' && ch>='0';ch=getchar()) tmp=tmp*10+ch-'0';
    return tmp;
}
int tot=0;
int pre[maxn],now[maxn],son[maxn];
inline void add(int a,int b){
	pre[++tot]=now[a];
	now[a]=tot;
	son[tot]=b;
}
bool used[maxn];
priority_queue<zy>h;
int n;
inline void prepare(){
	tot=0;
	memset(now,0,sizeof(int)*n);
	memset(used,0,sizeof(bool)*n);
	while (!h.empty()) h.pop();
}

int root;
int tim[maxn],v[maxn];
int fa[maxn];
void init(){
	n=getint()+1;
	prepare();
	n--;
	root=getint();
	for (int i=1;i<=n;++i){
		tim[i]=1;
		v[i]=getint();
		h.push(zy(i,v[i],1));
	}
	int a,b;
	for (int i=1;i<n;++i){
		a=getint();
		b=getint();
		add(a,b);
		fa[b]=a;
	}
}
inline int findmax(int root){
	while (used[h.top().num] || h.top().num==root) h.pop();
	return h.top().num;
}

inline int find(int x){
	if (used[fa[x]]) fa[x]=find(fa[x]);
	return fa[x];
}

inline void Union(int a,int b){
	v[b]+=v[a];
	tim[b]+=tim[a];
	for (int p=now[a];p;p=pre[p])
		fa[son[p]]=b;
}

void work(){
	int ans=0;
	for (int i=1;i<n;++i){
		int tmp=findmax(root);
		used[tmp]=1;
		int pre=find(tmp);
		ans+=tim[pre]*v[tmp];
		Union(tmp,pre);
		h.push(zy(pre,v[pre],tim[pre]));
	}
	ans+=v[root];
	printf("%d\n",ans);
}

int main()
{
	while (1){
		init();
		if (!root) break;
		work();
	}
	return 0;
}

Ps：时间还是蛮快的，在pku上进了第一版