#include "beechtree.h"
#include <bits/stdc++.h>
using namespace std;
struct treeseq {
list<vector<pair<int, long long>>> seq;
int size = 0;
};
vector<vector<pair<int, int>>> children;
vector<int> subtreesize;
vector<int> ret;
vector<vector<int>> subtree;
int getsubtreesize(int node, int parent) {
int res = 1;
subtree[node].push_back(node);
for(auto it = children[node].begin(); it != children[node].end(); it++) {
if(it->second == parent) {
children[node].erase(it);
break;
}
}
for(pair<int, int> e : children[node]) {
res += getsubtreesize(e.second, node);
for(int a : subtree[e.second]) subtree[node].push_back(a);
}
subtreesize[node] = res;
return res;
}
bool issubtree(int a, int b) { // is b subtree of a
vector<pair<int, int>>& ca = children[a];
vector<pair<int, int>>& cb = children[b];
for(int i = 1; i < ca.size(); i++) {
if(ca[i - 1].first == ca[i].first) return false;
}
for(int i = 1; i < cb.size(); i++) {
if(cb[i - 1].first == cb[i].first) return false;
}
for(int i = 0; i < ca.size(); i++) {
bool bb = false;
for(int j = 0; j < cb.size(); j++) {
if(ca[i].first == cb[j].first) {
bb = issubtree(ca[i].second, cb[j].second);
}
}
if(!bb) return false;
}
return true;
}
treeseq* merge(treeseq* left, treeseq* right) {
if(left == nullptr && right == nullptr) return nullptr;
if(left == nullptr) {
delete right;
return nullptr;
}
if(right == nullptr) {
delete left;
return nullptr;
}
if(left->size < right->size) {
treeseq* temp = left;
left = right;
right = temp;
}
return nullptr;
}
void dp(int node) {
for(pair<int, int> e : children[node]) dp(e.second);
bool res = true;
for(int a : subtree[node]) {
for(int b : subtree[node]) {
if(subtreesize[a] <= subtreesize[b]) res = res && issubtree(a, b);
else res = res && issubtree(b, a);
}
}
ret[node] = res;
}
vector<int> beechtree(int N, int M, vector<int> P, vector<int> C) {
children.resize(N);
subtreesize.resize(N);
subtree.resize(N);
ret.resize(N);
for(int i = 1; i < N; i++) {
children[P[i]].push_back(make_pair(C[i], i));
}
for(int i = 0; i < N; i++) {
sort(children[i].begin(), children[i].end());
}
getsubtreesize(0, -1);
dp(0);
return ret;
}
