#include "beechtree.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ALL(a) a.begin(), a.end()
const int MXN = 200200;
int n;
int m;
vector<int> p;
vector<int> c;
vector<int> adj[MXN];
bool leaf[MXN];
int ptr[MXN];
bool valid(vector<int> vec) {
bool ans = true;
for (auto it = next(vec.begin()); it != vec.end(); it++) {
if (vec.size() <= ptr[c[*it]] || vec[ptr[c[*it]]] != p[*it]) ans = false;
ptr[c[*it]]++;
}
for (int v : vec) ptr[c[v]] = 0;
return ans;
}
int h[MXN];
int sz[MXN];
bool cmp(int v, int u) {
if (h[v]==h[u]) return sz[v]>sz[u];
return h[v]<h[u];
}
vector<int> ans;
vector<int> dfs(int v) {
if (leaf[v]) {
ans[v] = 1;
return {v};
}
vector<int> norm{v}, esp;
for (int u : adj[v]) {
h[u] = h[v]+1;
auto vec = dfs(u);
sz[v] += sz[u];
for (int x : vec) (leaf[x] ? esp : norm).pb(x);
}
sort(ALL(norm), cmp);
sort(ALL(esp), [&](int x, int y) {
return cmp(p[x], p[y]);
});
vector<int> res;
for (int x : norm) res.pb(x);
for (int x : esp) res.pb(x);
ans[v] = valid(res);
return res;
}
vector<int> beechtree(int N, int M, vector<int> P, vector<int> C) {
n = N;
m = M;
p = P;
c = C;
for (int i=1; i<n; i++) adj[p[i]].pb(i);
for (int i=0; i<n; i++) leaf[i] = adj[i].empty();
ans.resize(n);
dfs(0);
return ans;
}
