// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>

#define sz(x) (int) x.size()
#define all(x) x.begin(), x.end()
#define edge pair<int, int>

using namespace std;

vector<vector<edge>> adj;
vector<int> subtreesz;
vector<int> ans;
vector<map<int, int>> nxt;
vector<int> color; // copy

void gensz(int c) {
	subtreesz[c] = 1;

	for (auto n : adj[c]) {
		gensz(n.first);
		subtreesz[c] += subtreesz[n.first];
	}
}

vector<set<pair<int, int>>> bk;

bool check(int a, int b) {
	// fuck u

	if (sz(adj[a]) > sz(adj[b])) {
		return false;
	}

	for (auto n : adj[a]) {
        if (nxt[b].find(color[n.first]) == nxt[b].end() || subtreesz[n.first] > subtreesz[nxt[b][color[n.first]]]) {
			return false;
		}
    }

    return true;
}

void dfs(int c) {
	// rip ur mom;

	for (auto n : adj[c]) {
		dfs(n.first);

		if (ans[n.first] == 0) {
			ans[c] = 0;
		}
	}

	if (ans[c] == 0) {
		return;
	}

	bk[c].insert({subtreesz[c], c});

	for (auto n : adj[c]) {
		if (sz(bk[c]) < sz(bk[n.first])) swap(bk[c], bk[n.first]);

        for (auto p : bk[n.first]) {
            auto it = bk[c].lower_bound(p);

            if (it != bk[c].end()) {
                if (!check(p.second, (*it).second)) {
                    ans[c] = 0; return;
                }
            }

            if (it != bk[c].begin()) {
                it = prev(it);

                if(!check((*it).second, p.second)) {
                    ans[c] = 0; return;
                }
            }

            bk[c].insert(p);
        }
    }
}

bool cmp(const pair<int, int> &a, const pair<int, int> &b) {
	return subtreesz[a.first] > subtreesz[b.first];
}

vector<int> beechtree(int N, int M, vector<int> P, vector<int> C) {
	ans.resize(N); fill(all(ans), 1); bk.resize(N); color.resize(N); nxt.resize(N);

	adj.resize(N); subtreesz.resize(N);

	for (int i = 0; i < N; i++) {
		adj[i].clear(); bk[i].clear(); color[i] = C[i]; nxt[i].clear();
	}

	for (int i = 1; i < N; i++) {
		adj[P[i]].push_back({i, C[i]});

		if (nxt[P[i]].find(C[i]) != nxt[P[i]].end()) {
			ans[P[i]] = 0;
		} else {
			nxt[P[i]][C[i]] = i;
		}
	}

	gensz(0);

	for (int i = 0; i < N; i++) {
		sort(all(adj[i]), cmp);
	}

	bk.resize(N);

	dfs(0);

	return ans;
}