fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define pb push_back
  4. int parent[1000005];
  5. int color[1000005];
  6. bool visited[1000005];
  7. int a[1000005];
  8. vector<int>adj[1000005];
  9. vector<int>ans[1000005];
  10. int res[1000005];
  11. int n,k;
  12. int c1,c2;
  13. void dfs(int ele)
  14. {
  15.  	visited[ele]=true;
  16.  	int flag=0;
  17.  	ans[color[ele]].pb(ele);
  18.  	if(ans[color[ele]].size()>k)
  19.  	{
  20.  		int size=ans[color[ele]].size();
  21.  		res[ele]=ans[color[ele]][size-k-1];
  22.  //		return ;
  23.  	}
  24.  	else
  25.  		 res[ele]=-1;
  26.  	for(int i=0;i<adj[ele].size();i++)
  27.  	{
  28.  		if(!visited[adj[ele][i]])
  29.  		{
  30.  		//	c1++;
  31.  
  32.  			//parent[adj[ele][i]]=ele;
  33.  			dfs(adj[ele][i]);
  34.  			if(ans[color[ele]].size()>0)
  35.  				ans[color[ele]].pop_back();
  36.  			//c2++;
  37.  		}
  38.  	}
  39. }
  40.  
  41. int main()
  42. {
  43.      ios_base::sync_with_stdio(false);
  44.     cin.tie(NULL);
  45. 	int x,y;
  46. 	cin>>n>>k;
  47. 	for(int i=1;i<=n;i++)
  48. 	{
  49. 		cin>>color[i];
  50. 	}
  51. 	for(int i=0;i<n-1;i++)
  52. 	{
  53. 		cin>>x>>y;
  54. 		adj[x].pb(y);
  55. 		adj[y].pb(x);
  56.  
  57. 	}
  58. 	parent[1]=-1;
  59. 	//memset(res,-1,1000001);
  60. 	dfs(1);
  61.  
  62.  
  63. 	for(int i=1;i<=n;i++)
  64. 	{
  65. 		cout<<res[i]<<" ";	
  66. 	}
  67. //	cout<<"c1 "<<c1<<" "<<c2<<endl;
  68. 	return 0;
  69. }
Success #stdin #stdout 0.01s 79552KB
comments (?)
stdin
copy 
7 2
1 1 2 1 2 2 1
1 3
1 2
2 4
2 5
5 6
5 7
stdout
copy 
-1 -1 -1 -1 -1 3 -1
https://ideone.com/BoXJZl
language:
C++14 (gcc 8.3)
created:
6 years 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!