/**
 * @file qoj7121-1.cpp
 * @author n685
 * @brief
 * @date 2023-12-29
 *
 *
 */
#include "beechtree.h"
#include <bits/stdc++.h>

#ifdef LOCAL
#include "dd/debug.h"
#else
#define dbg(...) 42
#define dbgR(...) 4242
#define dbgP(...) 420
#define dbgRP(...) 420420
void nline() {}
#endif

struct Tree {
  static constexpr int LG = 20;
  int n;
  const std::vector<std::vector<int>> &adj;
  std::vector<int> p, d, sub;
  std::vector<std::vector<int>> a;
  void dfs(int node, int par) {
    p[node] = par;
    for (int i : adj[node]) {
      if (i == par) {
        continue;
      }
      d[i] = d[node] + 1;
      dfs(i, node);
      sub[node] += sub[i];
    }
  }
  Tree(const std::vector<std::vector<int>> &_adj)
      : n((int)_adj.size()), adj(_adj), p(n, -1), d(n), sub(n, 1),
        a(LG, std::vector<int>(n, -1)) {
    dfs(0, -1);
    a[0] = p;
    for (int i = 1; i < LG; ++i) {
      for (int j = 0; j < n; ++j) {
        if (a[i - 1][j] != -1) {
          a[i][j] = a[i - 1][a[i - 1][j]];
        }
      }
    }
  }
  int up(int u, int dist) {
    if (dist < 0) {
      return -1;
    }
    if (d[u] < dist) {
      return -1;
    }
    for (int i = 0; i < LG; ++i) {
      if ((1 << i) & dist) {
        u = a[i][u];
      }
    }
    return u;
  }
  // is v an ancestor of u?
  bool ancestor(int u, int v) { return (up(u, d[u] - d[v]) == v); }

  int lca(int u, int v) {
    if (d[u] < d[v]) {
      std::swap(u, v);
    }
    for (int i = LG - 1; i >= 0; --i) {
      if (d[u] >= (1 << i) && !ancestor(v, a[i][u])) {
        u = a[i][u];
      }
    }
    return p[u];
  }
};

std::vector<int> beechtree(int N, int M, std::vector<int> P,
                           std::vector<int> C) {
  int n = N;
  std::vector<int> c = C;

  std::vector<std::vector<int>> adj(n);
  for (int i = 1; i < n; ++i) {
    adj[P[i]].push_back(i);
  }

  Tree tr(adj);
  std::vector<int> good(n, true);
  for (int i = 0; i < n; ++i) {
    std::sort(adj[i].begin(), adj[i].end(),
              [&](int a, int b) { return c[a] < c[b]; });
    for (int j = 0; j < (int)adj[i].size() - 1; ++j) {
      if (c[adj[i][j]] == c[adj[i][j + 1]]) {
        good[i] = false;
        break;
      }
    }
  }
  auto gg = [&](int a, int b, int par) {
    if (!good[a] || !good[b] || !good[par]) {
      return false;
    }
    if (tr.sub[a] > tr.sub[b]) {
      std::swap(a, b);
    }
    int r = 0;
    for (int l = 0; l < (int)adj[a].size(); ++l) {
      // while (r < (int)adj[b].size() && c[adj[a][l]] > c[adj[b][r]]) {
      //   r++;
      // }
      r = (int)std::distance(
          adj[b].begin(),
          std::lower_bound(adj[b].begin(), adj[b].end(), c[adj[b][r]],
                           [&](auto a, auto b) { return c[a] < b; }));
      if (r >= (int)adj[b].size() || c[adj[a][l]] < c[adj[b][r]] ||
          tr.sub[adj[a][l]] > tr.sub[adj[b][r]]) {
        return false;
      } else if (tr.sub[a] == tr.sub[b] &&
                 tr.sub[adj[a][l]] < tr.sub[adj[b][r]]) {
        return false;
      }
    }
    return true;
  };
  auto dfs = [&](auto &self, int node) -> std::set<std::pair<int, int>> * {
    if ((int)adj[node].size() == 0) {
      return new std::set{std::pair{tr.sub[node], node}};
    }
    std::set<std::pair<int, int>> *mx = nullptr;
    std::vector<std::set<std::pair<int, int>> *> v;
    for (int i : adj[node]) {
      auto s = self(self, i);
      if (!good[i]) {
        good[node] = false;
      }
      if (!mx) {
        mx = s;
      } else if (mx->size() < s->size()) {
        v.push_back(mx);
        mx = s;
      } else {
        v.push_back(s);
      }
    }
    for (auto s : v) {
      for (auto [$, i] : *s) {
        auto it = mx->lower_bound({tr.sub[i], i});
        if (it != mx->end()) {
          auto [$$, j] = *it;
          if (!gg(i, j, node)) {
            good[node] = false;
          }
        }
        if (it != mx->begin()) {
          auto [$$, j] = *std::prev(it);
          if (!gg(i, j, node)) {
            good[node] = false;
          }
        }
      }
      mx->merge(*s);
    }
    mx->insert(std::pair{tr.sub[node], node});
    return mx;
  };
  delete dfs(dfs, 0);
  return good;
}