In this HackerEarth Mancunian And Colored Tree problem solution After a hectic week at work, Mancunian and Liverbird decide to go on a fun weekend camping trip. As they were passing through a forest, they stumbled upon a unique tree of N nodes. Vertices are numbered from 1 to N.

Each node of the tree is assigned a color (out of C possible colors). Being bored, they decide to work together (for a change) and test their reasoning skills. The tree is rooted at vertex 1. For each node, they want to find its closest ancestor having the same color.

## HackerEarth Mancunian And Colored Tree problem solution.

```#include <iostream>
#include <stack>
#include <vector>
#define ff first
#define ss second
#define pb push_back
#define MOD (1000000007LL)
#define LEFT(n) (2*(n))
#define RIGHT(n) (2*(n)+1)

using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;

#define SIZE 100005
int n, C, col[SIZE], ans[SIZE];
stack<int> st[SIZE];

void dfs(int v){

if(st[col[v]].empty()){
ans[v] = -1;
}
else{
ans[v] = st[col[v]].top();
}

st[col[v]].push(v);

dfs(vv);
}

st[col[v]].pop();
}

int main(){

cin>>n>>C;
for(int i=2;i<=n;i++){
int p;
cin>>p;
}
for(int i=1;i<=n;i++)
cin>>col[i];

dfs(1);
for(int i=1;i<=n;i++)
cout<<ans[i]<<" ";
return 0;
}
```

### Second solution

```#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
vector <int> G[MAXN], col_list[MAXN];
int col[MAXN], ans[MAXN];
void dfs(int pos)
{
if(col_list[col[pos]].empty())
ans[pos] = -1;
else
ans[pos] = col_list[col[pos]].back();
col_list[col[pos]].push_back(pos);
for (int i = 0; i < G[pos].size(); ++i)
{
dfs(G[pos][i]);
}
col_list[col[pos]].pop_back();
}
int main()
{
int n,c;
cin>>n>>c;
for (int i = 2; i <= n; ++i)
{
int par;
cin>>par;
G[par].push_back(i);
}
for (int i = 1; i <= n; ++i)
{
cin>>col[i];
}
dfs(1);
for (int i = 1; i <= n; ++i)
{
cout<<ans[i]<<" ";
}
return 0;
}```