#include "beechtree.h"
#include <bits/stdc++.h>
using namespace std;
#define bug(x) cout << #x << " " << x << endl;
vector<vector<pair<int, int>>> adj;
vector<vector<int>> mask;
vector<int> ruim;
bool is_supermask( vector<int> &a, vector<int> &b ){
int p = 0;
for( int x : a ){
if( p == b.size() ) break;
if( b[p] == x ) p++;
}
return p == b.size();
}
void dfs( int cur, vector<int> &resp ){
resp[cur] = true;
for( auto [viz, cor] : adj[cur] ){
mask[cur].push_back(cor);
dfs( viz , resp );
resp[cur] &= resp[viz];
}
sort( mask[cur].begin(), mask[cur].end() );
for( int i = 1; i < mask[cur].size(); i++ ) if( mask[cur][i] == mask[cur][i - 1] ) resp[cur] = false;
sort( adj[cur].begin(), adj[cur].end(), [&]( pair<int, int> a, pair<int, int> b ){
return mask[a.first].size() < mask[b.first].size();
});
for( int i = 1; i < adj[cur].size(); i++ )
if( !is_supermask(mask[adj[cur][i].first], mask[adj[cur][i - 1].first] ) ) resp[cur] = false;
if( !adj[cur].empty() && !is_supermask(mask[cur], mask[adj[cur].back().first]) ) resp[cur] = false;
}
vector<int> beechtree(int n, int m, vector<int> p, vector<int> c ){
adj.resize(n);
mask.resize(n);
ruim.resize(n);
for( int i = 1; i < n; i++ ) adj[p[i]].push_back({ i, c[i] });
vector<int> resp(n);
dfs( 0, resp );
return resp;
}
