#include <bits/stdc++.h>
#include "beechtree.h"
using namespace std;
using ll = long long;
const int mxN = 2e5+10;
const int INF = 1e9+10;
int sz[mxN];
bool pos[mxN];
set<array<int, 2>> srt[mxN];
map<int, vector<int>> col[mxN];
bool check(int v, int u) {
for(auto [c, vec] : col[v]) {
auto it = col[u].find(c);
if(it == col[u].end() || sz[vec[0]] > sz[it->second[0]]) return false;
}
return true;
}
bool add(set<array<int, 2>> &srt, array<int, 2> p) {
auto [it, st] = srt.insert(p);
bool result = true;
if(it != srt.begin()) {
result &= check((*prev(it))[1], (*it)[1]);
}
if(next(it) != srt.end()) {
result &= check((*it)[1], (*next(it))[1]);
}
return result;
}
int dfs(int node) {
sz[node] = 1;
pos[node] = true;
for(auto [c, v] : col[node]) {
pos[node] &= (v.size() == 1);
for(auto it : v) {
int nxt = dfs(it);
if(nxt == -1) pos[node] = false;
else {
sz[node] += nxt;
}
if(pos[node]) {
if(srt[it].size() > srt[node].size()) swap(srt[it], srt[node]);
for(auto it1 : srt[it]) {
pos[node] &= add(srt[node], it1);
}
}
}
}
pos[node] &= add(srt[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(!col[p].count(c)) {
col[p][c] = vector<int>();
}
col[p][c].push_back(i);
}
dfs(0);
vector<int> ans(n);
for(int i = 0; i < n; i++) {
ans[i] = pos[i];
}
return ans;
}
