#include "beechtree.h"
#include <bits/stdc++.h>
using namespace std;
#define all(v) v.begin(), v.end()
const int M = 2e5 + 1;
vector<int> nei[M], v[M], ans;
vector<pair<int,pair<int,int>>> sub[M];
int dep[M];
bool vis[M];
void dfs(int u)
{
sub[u].push_back({M-dep[u],{v[u].size(),u}});
for (int i:nei[u])
{
dep[i]=dep[u]+1,dfs(i);
for (auto p:sub[i])
sub[u].push_back(p);
}
sort(all(sub[u]));
ans[u]=1;
for (int c=0;c+1<sub[u].size() && ans[u];c++)
{
int i=sub[u][c].second.second, j=sub[u][c+1].second.second;
ans[u]&=ans[i]&ans[j];
for (int x:v[j]) vis[x]=1;
for (int x:v[i])
if (!vis[x]) ans[u]=0;
for (int x:v[j]) vis[x]=0;
}
}
vector<int> beechtree(int n, int m, vector<int> p, vector<int> c)
{
vector<pair<int,int>> ch;
for (int i=n-1;i>0;i--)
nei[p[i]].push_back(i),v[p[i]].push_back(c[i]),
sort(all(v[i])),v[i].resize(unique(all(v[i]))-begin(v[i]));
ans=vector<int>(n);
dfs(0);
return ans;
}
