E. Lomsat gelral
Time Limit: 20 Sec
Memory Limit: 256 MB
题目连接
http://codeforces.com/contest/600/problem/E
Description
You are given a rooted tree with root in vertex 1. Each vertex is coloured in some colour.
Let's call colour c dominating in the subtree of vertex v if there are no other colours that appear in the subtree of vertex v more times than colour c. So it's possible that two or more colours will be dominating in the subtree of some vertex.
The subtree of vertex v is the vertex v and all other vertices that contains vertex v in each path to the root.
For each vertex v find the sum of all dominating colours in the subtree of vertex v.
Input
The first line contains integer n (1 ≤ n ≤ 105) — the number of vertices in the tree.
The second line contains n integers ci (1 ≤ ci ≤ n), ci — the colour of the i-th vertex.
Each of the next n - 1 lines contains two integers xj, yj (1 ≤ xj, yj ≤ n) — the edge of the tree. The first vertex is the root of the tree.
Output
Print n integers — the sums of dominating colours for each vertex.
Sample Input
4
1 2 3 4
1 2
2 3
2 4
Sample Output
10 9 3 4
HINT
题意
给你一棵树，告诉你每个节点的颜色，然后让你输出对于这个节点的子树中，出现次数最多的颜色的权值和是多少
题解：
启发式合并map
对于每一个子树，我们都维护一个map，然后从小的合并到大的中
均摊下来复杂度不会很高（雾
代码：
#include<iostream>
#include<stdio.h>
#include<vector>
#include<map>
using namespace std;
#define maxn 800005 map<int,int> H[maxn];
map<int,int>::iterator it;
long long ans[maxn];
vector<int> E[maxn];
int c[maxn];
int id[maxn];
long long M[maxn];
long long M1[maxn];
void uni(int &x,int y)
{
if(H[x].size()<H[y].size())swap(x,y);
for(it = H[y].begin();it!=H[y].end();it++)
{
H[x][it->first]+=it->second;
if(M1[x]==H[x][it->first])
M[x]+=it->first;
if(M1[x]<H[x][it->first])
{
M1[x]=H[x][it->first];
M[x]=it->first;
}
}
}
void solve(int x,int fa)
{
H[x][c[x]]=;
M1[x]=,M[x]=c[x];
for(int i=;i<E[x].size();i++)
{
if(E[x][i]==fa)continue;
solve(E[x][i],x);
uni(id[x],id[E[x][i]]);
}
ans[x]=M[id[x]];
}
long long flag = ;
int main()
{
int n;scanf("%d",&n);
for(int i=;i<=n;i++)
{
id[i]=i;
scanf("%d",&c[i]);
}
for(int i=;i<n;i++)
{
int x,y;scanf("%d%d",&x,&y);
E[x].push_back(y);
E[y].push_back(x);
}
solve(,-);
for(int i=;i<=n;i++)
printf("%lld ",ans[i]);
printf("\n");
return ;
}