#include "beechtree.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
vector<map<int, int> > m;
vector<int> sz, ans;
vector<set<pii> > s;
vector<vector<pii> > graph;
void dfs(int node){
sz[node]=1;
set<int> temp;
for (auto num:graph[node])dfs(num.fi), sz[node]+=sz[num.fi], temp.insert(num.se), ans[node]&=ans[num.fi];
if (temp.size()!=graph[node].size())ans[node]=0;
s[node].insert(mp(sz[node], node));
for (auto num:graph[node]){
if (s[node].size()<s[num.fi].size())swap(s[node], s[num.fi]);
for (auto a:s[num.fi]){
s[node].insert(a);
auto it = s[node].find(a);
if (it!=s[node].begin()){
--it;
for (auto c:m[it->se])if (!m[a.se].count(c.fi)||sz[c.se]>sz[m[a.se][c.fi]])ans[node]=0;
++it;
}
if (it!=s[node].end()){
++it;
for (auto c:m[a.se])if (!m[it->se].count(c.fi)||sz[c.se]>sz[m[it->se][c.fi]])ans[node]=0;
}
}
}
}
vector<int> beechtree(int n, int M, vector<int> p, vector<int> c){
graph.clear();
ans.clear();
sz.clear();
m.clear();
s.clear();
s.resize(n);
m.resize(n);
ans.resize(n, 1);
sz.resize(n);
graph.resize(n);
for (int i=1; i<n; ++i)graph[p[i]].pb(mp(i, c[i])), m[p[i]][c[i]]=i;
dfs(0);
return ans;
}
