#include "beechtree.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb push_back
mt19937_64 rng(time(0));
const int N = 2e5 + 5;
bool ok[N];
vector<array<int, 2>> ch[N];
ll cl[N];
int sz[N], c[N], dd[N];
void dfs(int s) {
set<int> st;
ok[s] = 1, sz[s] = 1;
for (auto [u, w] : ch[s]) {
if (st.count(w)) ok[s] = 0;
st.insert(w);
dfs(u);
sz[s] += sz[u], ok[s] &= ok[u], dd[s] = max(dd[u] + 1, dd[s]);
}
}
void dfscnt(int s, map<int, int> &f) {
for (auto [u, w] : ch[s]) {
f[w]++;
dfscnt(u, f);
}
}
bool chk(int s) {
map<int, int> f;
ll h[sz[s]];
fill(h, h+sz[s], 0);
dfscnt(s, f);
for (auto [x, y] : f) {
// if (s == 0) cout << x << 'z' << y << endl;
for (int i = 0; i < y; ++i) h[i] ^= cl[x];
}
map<int, int> t, t2, t3;
set<array<ll, 4>> st;
ll xx = 0;
for (auto [u, w] : ch[s]) {
xx ^= cl[w];
// if (s == 0) cout << w << '|';
ll x = 0;
for (auto [v, W] : ch[u]) x ^= cl[W];
t[u] = t2[w];
t2[w]++;
st.insert({x, -sz[u], t[u], u});
}
// if (s == 0) cout << xx << ' ' << h[0] << endl;
if (xx != h[0]) return 0;
// if (s == 2) {
// for (auto [p, q, r, t] : st) cout << p << ' ' << q << ' ' << r << '\n';
// cout << h[1] << 't' << h[2] << '\n';
// for (auto [x, y] : f) {
// cout << x << " " << y << '\n';
// }
// }
for (int i = 1; i < sz[s]; ++i) {
auto it = st.lower_bound({h[i], (int)-1e9, 0, 0});
if ((*it)[0] != h[i]) return 0;
int x = (*it)[3];
it = st.erase(it);
// if (s == 2) cout << x << ' ' << t[x] << ' ' << ' ' << t3[c[x]] << '\n';
if (t[x] != t3[c[x]]) return 0;
t3[c[x]]++;
for (auto [u, w] : ch[x]) {
ll xx = 0;
for (auto [v, W] : ch[u]) xx ^= cl[W];
t[u] = t2[c[u]];
t2[c[u]]++;
// if (s == 4) cout << xx << 'z' << u << '\n';
st.insert({xx, -sz[u], t[u], u});
}
}
return 1;
}
vector<int> beechtree(int n, int m, vector<int> P, vector<int> C) {
for (int i = 1; i < n; ++i) ch[P[i]].pb({i, C[i]});
for (int i = 1; i <= m; ++i) cl[i] = rng() % (1LL << 62);
for (int i = 1; i < n; ++i) c[i] = C[i];
dfs(0);
vector<int> ans(n);
for (int i = 0; i < n; ++i) ans[i] = (ok[i] && dd[i] <= 2 ? chk(i) : 0);
return ans;
}
