#include <bits/stdc++.h>
using namespace std;
vector<int> beechtree(int N, int M, vector<int> P, vector<int> C) {
vector<vector<int>> adj(N);
for (int i = 1; i < N; ++i) {
adj[P[i]].push_back(i);
}
vector<int> ans(N);
auto check_good = [&](int U) {
vector<vector<int>> subts;
int bad = 0;
auto dfs = [&](auto &&self, int u) -> vector<int> {
vector<int> a;
for (int &i : adj[u]) {
auto ch = self(self, i);
for (int &i : ch) a.push_back(i);
}
set<int> st;
for (int &i : adj[u]) st.insert(C[i]);
if (st.size() == adj[u].size()) {
if (u != U) {
ans[u] = 1;
subts.push_back(a);
}
} else {
bad = 1;
}
a.push_back(C[u]);
return a;
};
dfs(dfs, U);
sort(subts.begin(), subts.end(), [&](vector<int> &a, vector<int> &b) { return a.size() < b.size(); });
subts.emplace_back();
for (auto &i : adj[U]) subts.back().push_back(C[i]);
for (auto &sub : subts) {
sort(sub.begin(), sub.end());
}
for (int i = 0; i < int(subts.size()) - 1; ++i) {
for (auto &e : subts[i]) {
if (!binary_search(subts[i + 1].begin(), subts[i + 1].end(), e)) {
bad = 1;
}
}
}
ans[0] = !bad;
};
vector<int> dep(N);
auto dfs = [&](auto &&self, int u) -> int {
int ans = 0;
for (int &i : adj[u]) {
dep[i] = dep[u] + 1;
ans = max(ans, self(self, i));
}
ans = max(ans, dep[u]);
if (ans - dep[u] <= 2) {
check_good(u);
}
return ans;
};
dfs(dfs, 0);
return ans;
}
