[Codeforces] E. Lomsat gelral

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : E. Lomsat gelral
Source            : Codeforces
Category          : Graph Theory
Algorithm         : Union By Rank
Verdict           : Accepted

#include "bits/stdc++.h"  
  
using namespace std;  
  
#define ll            long long  
#define sz(a)         (int)a.size()  
  
static const int maxn = 2e5 + 5;  
  
vector <int> graph[maxn];  
ll color[maxn];  
map <ll, ll> mapper[maxn]; // mapper[ parent node ][ color ] = occurrence for node u  
ll maxOcc[maxn];           // maximum occurrence in node u  
ll cnt[maxn];  
ll ans[maxn];  
int p[maxn];  
  
void marge(int a, int b)  
{  
    if (sz(mapper[ p[a] ]) < sz(mapper[ p[b] ])) swap(p[a], p[b]);  
    int id = p[a];  
    for (auto it : mapper[ p[b] ])  
    {  
        ll col = it.first;  
        ll occ = it.second;  
        mapper[id][col] += occ;  
        if (mapper[id][col] > maxOcc[id])  
        {  
            maxOcc[id] = mapper[id][col];  
            cnt[id] = col;  
        }  
        else if (mapper[id][col] == maxOcc[id])  
        {  
            cnt[id] += col;  
        }  
    }  
}  
  
void dfs(int u = 1, int par = -1)  
{  
    for (int v : graph[u])  
    {  
        if (v == par) continue;  
        dfs(v, u);  
        marge(u, v);  
    }  
    ans[u] = cnt[ p[u] ];  
}  
  
int main()  
{  
    //freopen("in.txt", "r", stdin);  
  
    int tnode;  
    scanf("%d", &tnode);  
    for (int i = 1; i <= tnode; i++)  
    {  
        scanf("%lld", color+i);  
        mapper[i][ color[i] ] = 1;  
        maxOcc[i] = 1;  
        cnt[i] = color[i];  
        p[i] = i;  
    }  
    for (int e = 1; e < tnode; e++)  
    {  
        int u, v;  
        scanf("%d %d", &u, &v);  
        graph[u].emplace_back(v);  
        graph[v].emplace_back(u);  
    }  
    dfs();  
    for (int i = 1; i <= tnode; i++) printf("%lld ", ans[i]);  
}