http://codeforces.com/contest/600/problem/E

暴力启发式合并就行了

提示：set的swap的复杂度是常数，这方面可以放心

我先打了一个很naive的算法

#include
#include
#include
#include
#include

s;
//P(颜色出现次数，颜色编号)
typedef map m;
//颜色编号->颜色出现次数
typedef pair P2;
LL n,anss[],c[];
vector e[];
P2 dfs(LL u,LL fa)
{
P2 t,ans;
ans.first.emplace(,c[u]);
ans.second[c[u]]=;
for(auto v:e[u])
if(v!=fa)
{
t=dfs(v,u);
if(t.second.size()>ans.second.size()) swap(t,ans);
for(auto it:t.second)
{
ans.first.erase(P(ans.second[it.first],it.first));
ans.second[it.first]+=it.second;
ans.first.emplace(ans.second[it.first],it.first);
}
}
int maxsz=ans.first.rbegin()->first;
for(auto it=ans.first.rbegin();it!=ans.first.rend()&&it->first==maxsz;it++) anss[u]+=it->second;
return ans;
}
int main()
{
LL i,x,y;
scanf("%lld",&n);
for(i=;i<=n;i++) scanf("%lld",&c[i]);
for(i=;i<n;i++)
{
scanf("%lld%lld",&x,&y);
e[x].push_back(y);e[y].push_back(x);
}
dfs(,);
for(i=;i<=n;i++) printf("%lld ",anss[i]);
return ;
}

毫不意外的被卡掉了～看第34行，怎么看都不对嘛

有两种解决方法：

第一种：每一个节点dfs的时候额外返回一个值，记录当前子树的答案。

第二种：将set换成另一个map，记录颜色出现次数->编号之和

#include
#include
#include
#include

也可以将每个节点dfs返回的值改成全局变量（似乎可以避免一些玄学的常数问题）