Shared code

// Problem: Distinct Colors
// Contest: CSES - CSES Problem Set
// URL: https://cses.fi/problemset/task/1139
// Memory Limit: 512 MB
// Time Limit: 1000 ms

/*

WINNERS NEVER QUIT AND QUITTERS NEVER WIN!!

Falling down is an accident, Staying down is a choice.

*/

//region template

#include <bits/stdc++.h>
#include <bits/extc++.h>

using namespace std;
using namespace __gnu_pbds;

#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define memset0(x,i) memset(x,i,sizeof(x))
#define count1 __builtin_popcount
#define lead0 __builtin_clz
#define trail0 __builtin_ctz
#define min(...) _min(__VA_ARGS__)
#define max(...) _max(__VA_ARGS__)
#define FOR(i,l,r) for(int i=l;i<r;++i)
#define FORe(i,l,r) for(int i=l;i<=r;++i)
#define ROF(i,l,r) for(int i=r-1;i>=l;--i)
#define ROFe(i,l,r) for(int i=r;i>=l;--i)
#define trav(a,v) for(auto&a:v)
using ll = long long;
using vi = vector<int>;
using pii = pair<int,int>;
using db = double;
using ld = long double;
template<size_t x>struct lg2{enum{v=1+lg2<(x>>1)>::v};};template<>struct lg2<0>{enum{v=0};};
inline ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
inline ll cdiv(ll a,ll b){return a/b+((a^b)>0&&a%b);}
inline ll fdiv(ll a,ll b){return a/b-((a^b)<0&&a%b);}
bool prime(int n){if(n%2==0||n%3==0)return false;for(int i=5;i*i<=n;i+=6)if(n%i==0||n%(i+2)==0)return false;return true;}
template<class T>using set2 = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
template<class T1,class T2>using map2 = tree<T1,T2,less<T1>,rb_tree_tag,tree_order_statistics_node_update>;
template<class T>using heap = __gnu_pbds::priority_queue<T,greater<T>,pairing_heap_tag>;
template<class T>using max_heap = __gnu_pbds::priority_queue<T,less<T>,pairing_heap_tag>;
template<class T1,class T2>using unordered_map2 = gp_hash_table<T1,T2>;
template<class T1,class T2>unordered_map2<T1,T2> unordered_map2_size(int exp2){
    return unordered_map2<T1,T2>({},{},{},{},{(uint32_t)1<<exp2});}
template<class T>using unordered_set2 = unordered_map2<T,null_type>;
template<class T>unordered_set2<T> unordered_set2_size(int exp2) {return unordered_map2_size<T,null_type>(exp2);}
template<class T>constexpr const T&_min(const T&x,const T&y){return x<y?x:y;}
template<class T>constexpr const T&_max(const T&x,const T&y){return x<y?y:x;}
template<class T,class...Ts>constexpr const T&_min(const T&x,const Ts&...xs){return _min(x,_min(xs...));}
template<class T,class...Ts>constexpr const T&_max(const T&x,const Ts&...xs){return _max(x,_max(xs...));}
template<class A> void re(complex<A>& c);
template<class A, class B> void re(pair<A,B>& p);
template<class A> void re(vector<A>& v);
template<class A, size_t SZ> void re(array<A,SZ>& a);
template<class T> void re(T& x) { cin >> x; }
void re(db& d) { string t; re(t); d = stod(t); }
void re(ld& d) { string t; re(t); d = stold(t); }
template<class H, class... T> void re(H& h, T&... t) { re(h); re(t...); }
template<class A> void re(complex<A>& c) { A a,b; re(a,b); c = {a,b}; }
template<class A, class B> void re(pair<A,B>& p) { re(p.fi,p.se); }
template<class A> void re(vector<A>& x) { trav(a,x) re(a); }
template<class A, size_t SZ> void re(array<A,SZ>& x) { trav(a,x) re(a); }
template<class A> void pr(A x) { cout << x; }
template<class H, class... T> void pr(const H& h, const T&... t) { pr(h); pr(t...); }
void ps() { pr("\n"); } // print w/ spaces
template<class H, class... T> void ps(const H& h, const T&... t) { pr(h); if (sizeof...(t)) pr(" "); ps(t...); }
void setIO(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
#ifdef IS_DEBUG
    freopen("../input.txt", "r", stdin);
#endif
}
namespace std{template<class T1,class T2> struct hash<pair<T1,T2>>{
    size_t operator()(const pair<T1,T2>&p)const{return 31*hash<T1>{}(p.fi)+hash<T2>{}(p.se);}
};}
template<class T>struct BIT{
    T n,*a;
    T sum(int i){T s=0;for(i++;i>0;i-=i&-i)s+=a[i];return s;}
    void edit(int i,T x){for(i++;i<=n;i+=i&-i)a[i]+=x;}
    void init(int m){n=m;a=new T[n+1]();}
    void init(T*arr,int m){init(m);FOR(i,0,n)edit(i,arr[i]);}
    BIT()=default;BIT(T*arr,int m){init(arr,m);}~BIT(){delete[]a;}
};
//endregion

const int MxN = 200001;
int N;
int color[MxN];
vi adj[MxN];
int ans[MxN];

using T = unordered_set2<int>;

T dfs(int a, int p) {
    T t;
    t.insert(color[a]);
    trav(b, adj[a]) {
        if (b != p) {
            T t1 = dfs(b, a);
            if (t1.size() > t.size()) {
                t.swap(t1);
            }
            trav(c, t1) {
                t.insert(c);
            }
        }
    }
    ans[a] = t.size();
    return t;
}

int main() {
    setIO();

    re(N);
    FOR(i, 0, N) re(color[i]);
    FOR(i, 1, N) {
        int a, b; re(a, b);
        a--, b--;
        adj[a].pb(b);
        adj[b].pb(a);
    }
    dfs(0, 0);
    pr(ans[0]);
    FOR(i, 1, N) {
        pr(' ', ans[i]);
    }
    ps();

    return 0;
}