fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3.  
  4. using namespace std;
  5.  
  6. constexpr int N = 2e5 + 5;
  7. int n;
  8. set<int> adj[N];
  9. vector<int> tree[N], col(N), par(N), ans(N);
  10.  
  11. int find(int u){
  12.     if(u == par[u]){
  13.         return u;
  14.     }
  15.     return par[u] = find(par[u]);
  16. }
  17.  
  18. void unite(int x, int y){
  19.     x = find(x);
  20.     y = find(y);
  21.     if (x == y)
  22.         return ;
  23.     if(adj[x].size() < adj[y].size()) swap(x, y);
  24.     par[y] = x;
  25.     for(int v : adj[y]){
  26.         adj[x].insert(v);
  27.     }
  28. }
  29.  
  30. void dfs(int u, int p){
  31.     for(int v : tree[u]){
  32.         if(v != p){
  33.             dfs(v, u);
  34.             unite(u, v);
  35.         }
  36.     }
  37.     ans[u] = adj[find(u)].size();
  38. }
  39.  
  40. signed main(){
  41.     ios_base::sync_with_stdio(false);
  42.     cin.tie(nullptr);
  43.     cout.tie(nullptr);
  44.     cin >> n;
  45.     for(int i = 1; i < n + 1; i++){
  46.         cin >> col[i];
  47.         adj[i].insert(col[i]);
  48.         par[i] = i;
  49.     }
  50.     for(int i = 1; i < n; i++){
  51.         int u, v;
  52.         cin >> u >> v;
  53.         tree[u].push_back(v);
  54.         tree[v].push_back(u);
  55.     }
  56.     dfs(1, -1);
  57.     for(int i = 1; i < n + 1; i++){
  58.         cout << ans[i] << " ";
  59.     }
  60.     cout << "\n";
  61.     return 0;
  62. }
  63.  
Success #stdin #stdout 0.01s 19476KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 

	

		
	 
	
	
			

					
			
			
			
			
			
			
			
			

			
			
			
		

	
		
		

			

			                        







			
			

				

	
					
					 https://ideone.com/xBBNuG
					
					
					
					
					

												

												
						
						

					

					
					
					

						
language:

						
C++14 (gcc 8.3)

					

					

						
created:
								
						
14 hours ago

					

					

						
visibility:

						

							 public																												
							
							

								
							

						

					

										
										

					
					 Share or Embed source code
					
					
					
					

						
						
						
						
						
						
						
					

					
						
	
	
	
	
					
					
					
					
					 
					
					
					
					 
					
					
					
					
					
					

					

					

					
						
					

					


	
Discover > Sphere Engine API

	
The brand new service which powers Ideone!

	
	
Discover > IDE Widget

    
Widget for compiling and running the source code in a web browser!