#include <bits/stdc++.h>
#include "beechtree.h"
using namespace std;
using ll = long long;
const int mxN = 2e5+10;
int sz[mxN];
bool pos[mxN];
map<int, vector<int>> adj[mxN];
set<pair<int, int>> vals[mxN];
bool check(int v, int u) {
for(auto [color, vec] : adj[v]) {
auto it = adj[u].find(color);
if(it == adj[u].end() || sz[vec[0]] > sz[it->second[0]]) {
return false;
}
}
return true;
}
bool add(set<pair<int, int>> &st, pair<int, int> elem) {
bool result = true;
auto [it, it2] = st.insert(elem);
if(it != st.begin()) {
result &= check(prev(it)->second, it->second);
}
if(next(it) != st.end()) {
result &= check(it->second, next(it)->second);
}
return result;
}
int dfs(int node) {
sz[node] = 1;
pos[node] = true;
for(auto [color, v] : adj[node]) {
pos[node] &= (v.size() == 1);
for(auto it : v) {
int nxt_sz = dfs(it);
if(nxt_sz == -1) pos[node] = false;
if(pos[node]) sz[node] += nxt_sz;
if(pos[node]) {
if(vals[it].size() > vals[node].size()) swap(vals[it], vals[node]);
for(auto it1 : vals[it]) {
pos[node] &= add(vals[node], it1);
}
}
}
}
pos[node] &= add(vals[node], {sz[node], node});
return pos[node] ? sz[node] : -1;
}
vector<int> beechtree(int n, int m, vector<int> P, vector<int> C) {
for(int i = 1; i < n; i++) {
int p = P[i], c = C[i];
if(adj[p].count(c) == 0) {
adj[p][c] = vector<int>();
}
adj[p][c].push_back(i);
}
dfs(0);
vector<int> ans(n);
for(int i = 0; i < n; i++) {
ans[i] = pos[i];
}
return ans;
}
