首页 > 代码库 > codeforces600E Lomsat gelral

codeforces600E Lomsat gelral

本文版权归ljh2000和博客园共有,欢迎转载,但须保留此声明,并给出原文链接,谢谢合作。

 

 

本文作者:ljh2000
作者博客:http://www.cnblogs.com/ljh2000-jump/
转载请注明出处,侵权必究,保留最终解释权!

 

题目链接:codeforces600E

正解:启发式合并

解题报告:

  这道题求的是每个点的子树内的出现次数最大的数字的和。

  考虑启发式合并,我用$col[x]$的$map$表示$x$的子树内的每种权值的出现次数,$sum[x]$的$map$表示$x$的子树内每种出现次数的权值和。

  那么我在将儿子节点和父亲节点合并的时候只需要根据$col$的$size$,把小的往大的里面暴力合并就可以了。

  $get$了$map$的正确姿势…

 

//It is made by ljh2000
//有志者,事竟成,破釜沉舟,百二秦关终属楚;苦心人,天不负,卧薪尝胆,三千越甲可吞吴。
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <ctime>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <complex>
#include <bitset>
using namespace std;
typedef long long LL;
typedef long double LB;
const double pi = acos(-1);
const int MAXN = 100011;
const int MAXM = 200011;
int n,a[MAXN],ecnt,first[MAXN],to[MAXM],next[MAXM];
LL ans[MAXN];
map<int,int>col[MAXN];//统计每种颜色的出现次数
map<int,LL>sum[MAXN];//统计每种出现次数的sum
inline void link(int x,int y){ next[++ecnt]=first[x]; first[x]=ecnt; to[ecnt]=y; }
inline int getint(){
    int w=0,q=0; char c=getchar(); while((c<‘0‘||c>‘9‘) && c!=‘-‘) c=getchar();
    if(c==‘-‘) q=1,c=getchar(); while (c>=‘0‘&&c<=‘9‘) w=w*10+c-‘0‘,c=getchar(); return q?-w:w;
}

inline void dfs(int x,int fa){
	col[x][a[x]]=1;
	sum[x][1]=a[x];
	int now,cc;
	for(int i=first[x];i;i=next[i]) {
		int v=to[i]; if(v==fa) continue;
		dfs(v,x);
		if(col[x].size()<col[v].size()) swap(col[x],col[v]),swap(sum[x],sum[v]);//小的往大的上面合并!!!
		for(map<int,int>::iterator it=col[v].begin();it!=col[v].end();it++) {
			now=it->first; cc=it->second;
			if(col[x].count(now)>0) {
				sum[x][col[x][now]]-=now;
				col[x][now]+=cc;
				sum[x][col[x][now]]+=now;
			}
			else col[x][now]=col[v][now],sum[x][col[x][now]]+=now;
		}
	}
	map<int,LL>::iterator it=sum[x].end();
	it--;//最大的应该是end-1,end是一个空指针...
	ans[x]=it->second;
}

inline void work(){
	n=getint(); for(int i=1;i<=n;i++) a[i]=getint(); int x,y;
	for(int i=1;i<n;i++) { x=getint(); y=getint(); link(x,y); link(y,x); }
	dfs(1,0);
	for(int i=1;i<=n;i++)
		printf("%I64d ",ans[i]);
}

int main()
{
    work();
    return 0;
}
//有志者,事竟成,破釜沉舟,百二秦关终属楚;苦心人,天不负,卧薪尝胆,三千越甲可吞吴。

  

codeforces600E Lomsat gelral