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
     
      #include
      
       #include
       
        #include
        using namespace std;#define maxn 800005map
         
           H[maxn];map
          
           ::iterator it;long long ans[maxn];vector
           
             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()
            
             first]+=it->second; if(M1[x]==H[x][it->first]) M[x]+=it->first; if(M1[x]
             
              first]) { M1[x]=H[x][it->first]; M[x]=it->first; } }}void solve(int x,int fa){ H[x][c[x]]=1; M1[x]=1,M[x]=c[x]; for(int i=0;i

转载地址：http://vmidx.baihongyu.com/

你可能感兴趣的文章