Mancunian And Colored Tree

4.cpp

#include "bits/stdc++.h"
using namespace std;

#define endl '\n'
#define mp make_pair
#define int long long
#define pb push_back
#define vi vector<int>
#define vvi vector<vector<int>>
#define ar array
#define ll long long
#define ld long double
#define sza(x) ((int)x.size())
#define all(a) (a).begin(), (a).end()

const int max_n = 1e5 + 5;
const ll mod = 1e9 + 7;
const ll M = 1e9;
const ll inf = 1e9;
const ld eps = 1e-9;

void setio(string name = "") {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  if (!name.empty()) {
    freopen((name + ".txt").c_str(), "r", stdin);
    freopen((name + ".out").c_str(), "w", stdout);
  } else {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
  }
}
int dx[8] = {1, -1, 0, 0, 1, 1, -1, -1};
int dy[8] = {0, 0, 1, -1, 1, -1, -1, 1};
int hdx[] = {-1, -2, -2, -1, 1, 2, 2, 1};
int hdy[] = {-2, -1, 1, 2, 2, 1, -1, -2};
bool inside(int x, int y, int n, int m) {
  return x >= 0 && x < n && y >= 0 && y < m;
}

vector<vector<int>> adj;
vector<int> color;
vector<stack<int>> order;
vector<int> res;

void dfs(int v) {
  if (order[color[v]].empty()) {
    res[v] = -1;
  } else {
    res[v] = order[color[v]].top();
  }
  order[color[v]].push(v);
  for (int u : adj[v]) {
    dfs(u);
  }
  order[color[v]].pop();
}
void solve() {
  int n;
  cin >> n;
  int c;
  cin >> c;
  adj.resize(n + 1);
  color.resize(n + 1);
  order.resize(c + 1);
  res.resize(n + 1, -1);
  for (int i = 1; i <= n - 1; i++) {
    int p;
    cin >> p;
    adj[p].push_back(i + 1);
  }
  for (int i = 1; i <= n; i++) {
    cin >> color[i];
  }
  dfs(1);
  for (int i = 1; i <= n; i++) {
    cout << res[i] << " ";
  }
  cout << endl;
}

int32_t main() {
  setio();
  int tc = 1;
  auto start_time = clock();
  // cin >> tc;
  for (int t = 1; t <= tc; t++) {
    // cout << "case #" << t << ": ";
    solve();
  }
  auto end_time = clock();
#ifndef ONLINE_JUDGE
  cout << "Time taken:" << (double)(end_time - start_time) / CLOCKS_PER_SEC
       << "s" << endl;
#endif
  return 0;
}