#include "beechtree.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <queue>
using namespace std;
const int N = 2e5 + 10;
vector <vector<pair<int, int>>> G;
vector <pair<int, int>> get_subtree(int v, int c) {
vector <pair<int, int>> cur;
cur.push_back({ v, c });
for (auto it : G[v]) {
for (auto& j : get_subtree(it.first, it.second)) {
cur.push_back(j);
}
}
return cur;
}
bool check(vector <pair<int, int>>& w, vector <int>& P, vector <int>& C) {
map <int, int> mp;
for (int i = 1; i < (int)w.size(); i++) {
if (P[w[i].first] != w[mp[w[i].second]].first) return false;
mp[w[i].second]++;
}
return true;
}
bool cmp(set <int> x, set <int> y) {
return (int)x.size() > (int)y.size();
}
vector <int> beechtree(int N, int M, vector <int> P, vector <int> C) {
bool subtask1 = (N <= 8);
bool subtask2 = true;
bool subtask3 = true;
bool subtask4 = true;
bool subtask5 = (N <= 200);
G.clear();
G.resize(N);
map <int, int> mp;
for (int i = 1; i < N; i++) {
if (P[i] != (i - 1)) {
subtask2 = false;
}
G[P[i]].push_back({ i, C[i] });
mp[C[i]]++;
if (P[i] != 0 && P[P[i]] != 0) {
subtask3 = false;
}
}
for (auto it : mp) {
if (it.second > 2) {
subtask4 = false;
}
}
if (subtask1) {
vector <int> ret = {};
for (int i = 0; i < N; i++) {
vector <pair<int, int>> w = get_subtree(i, C[i]);
sort(w.begin() + 1, w.end());
bool ch = false;
if (check(w, P, C)) ch = true;
while (next_permutation(w.begin() + 1, w.end())) {
if (check(w, P, C)) ch = true;
}
ret.push_back(ch);
}
return ret;
}
if (subtask2) {
vector <int> ret = {};
if (N == 1) return { 1 };
int cnt = 2;
for (int i = N - 2; i > 0; i--) {
if (C[i] != C[N - 1]) break;
cnt++;
}
for (int i = 0; i < N - cnt; i++) {
ret.push_back(0);
}
for (int i = 0; i < cnt; i++) {
ret.push_back(1);
}
return ret;
}
if (subtask3) {
bool esim = true;
vector <int> ret(N, 0);
vector <set<int>> sets;
for (int i = N - 1; i >= 1; i--) {
if (G[i].empty()) {
ret[i] = 1;
}
else {
bool ch = true;
set <int> ms;
for (auto it : G[i]) {
if (ms.find(it.second) != ms.end()) {
esim = false;
ch = false;
}
ms.insert(it.second);
}
if (ch) {
ret[i] = 1;
sets.push_back(ms);
}
}
}
if (!esim) return ret;
set <int> ms;
for (auto it : G[0]) {
if (ms.find(it.second) != ms.end()) {
return ret;
}
ms.insert(it.second);
}
sort(sets.begin(), sets.end(), cmp);
for (auto& it : sets) {
for (auto& j : it) {
if (ms.find(j) == ms.end()) {
return ret;
}
}
ms = it;
}
ret[0] = 1;
return ret;
}
if (subtask4) {
vector <int> ret(N, 0);
vector <bool> lvl1(N, 0);
vector <bool> different(N, true);
vector <set<int>> sets(N, set<int>());
for (int v = N - 1; v >= 0; v--) {
if (G[v].empty()) {
ret[v] = 1;
continue;
}
lvl1[v] = true;
for (auto& it : G[v]) {
if (!G[it.first].empty()) lvl1[v] = false;
}
if (lvl1[v]) {
for (auto& it : G[v]) {
if (sets[v].find(it.second) != sets[v].end()) {
different[v] = false;
}
sets[v].insert(it.second);
}
if (different[v]) {
ret[v] = 1;
continue;
}
}
bool lvl2 = true;
for (auto it : G[v]) {
if (!G[it.first].empty() && !lvl1[it.first]) {
lvl2 = false;
}
}
if (!lvl2) continue;
bool ch = true;
for (auto it : G[v]) {
if (!different[it.first]) ch = false;
}
set <int> ms;
for (auto it : G[v]) {
if (ms.find(it.second) != ms.end()) {
ch = false;
}
ms.insert(it.second);
}
vector <set<int>> cur_sets;
for (auto it : G[v]) {
if (!G[it.first].empty()) cur_sets.push_back(sets[it.first]);
}
sort(cur_sets.begin(), cur_sets.end(), cmp);
for (auto& it : cur_sets) {
for (auto& j : it) {
if (ms.find(j) == ms.end()) {
ch = false;
}
}
ms = it;
}
ret[v] = ch;
}
return ret;
}
if (subtask5) {
vector <int> ret(N, 1);
vector <set<int>> sets(N, set<int>());
vector <bool> ch(N, true);
for (int v = N - 1; v >= 0; v--) {
for (auto it : G[v]) {
if (!ch[it.first]) ch[v] = false;
}
for (auto it : G[v]) {
if (sets[v].find(it.second) != sets[v].end()) {
ch[v] = false;
}
sets[v].insert(it.second);
}
if (ch[v]) {
priority_queue <pair<pair<pair<int, int>, int>, set<int>>> Q;
set <int> ms = sets[v];
Q.push({ { make_pair(0, (int)G[v].size()), v}, sets[v] });
while (!Q.empty()) {
pair<pair<pair<int, int>, int>, set<int>> x = Q.top(); Q.pop();
for (auto it : x.second) {
if (ms.find(it) == ms.end()) {
ret[v] = 0;
}
}
ms = x.second;
for (auto& it : G[x.first.second]) {
Q.push({{ { x.first.first.first - 1, (int)G[it.first].size()}, it.first }, sets[it.first]});
}
}
}
else {
ret[v] = 0;
}
}
return ret;
}
return {};
}
/*
int main() {
for (auto it : beechtree(18, 3, { -1, 0, 0, 0, 1, 1, 1, 2, 2, 3, 3, 3, 4, 4, 5, 10, 11, 11 }, { 0, 1, 2, 3, 1, 2, 3, 1, 3, 3, 2, 1, 1, 2, 2, 1, 2, 3 })) {
cout << it << " ";
}
}
*/
