首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。