#include <bits/stdc++.h>
using namespace std;
int color[200005];
vector<pair<int, int>> v[200005];
vector<int> lc;
void Dfs(int g)
{
lc.push_back(g);
for(auto to: v[g])
{
Dfs(to.first);
}
}
int gag[200005];
int han[200005];
int timin[200005];
int timout[200005];
int ti = 1;
void Dfs1(int g)
{
timin[g]=ti++;
for(auto to: v[g])
{
Dfs1(to.first);
}
timout[g] = ti++;
}
bool stug(int a, int b)
{
if(timin[a] <= timin[b] && timout[a] >= timout[b])
{
return 1;
}
return 0;
}
pair<int, int> zuyg[200005];
void Dfs2(int g)
{
for(auto to: v[g])
{
Dfs2(to.first);
han[g] += han[to.first];
}
}
vector<int> beechtree(int N, int M, vector<int> P, vector<int> C)
{
vector<int> ans(N, 0);
if(N <= 8)
{
for(int i = 1; i < N; i++)
{
v[P[i]].push_back({i, C[i]});
}
for (int i = 0; i < N; i++)
{
lc.clear();
Dfs(i);
int stpereb = 0;
sort(lc.begin(), lc.end());
do
{
int st = 1;
if(lc[0] == i)
{
for (int j = 1; st && j < lc.size(); j++)
{
if(P[lc[j]] != lc[color[C[lc[j]]]])
{
st = 0;
for (int j = 0; j < lc.size(); j++)
{
color[C[lc[j]]] = 0;
}
break;
}
color[C[lc[j]]]++;
}
if(st)
{
stpereb = 1;
}
}
for (int j = 0; j < lc.size(); j++)
{
color[C[lc[j]]] = 0;
}
if(stpereb)break;
} while (next_permutation(lc.begin(), lc.end()));
if(stpereb)
ans[i] = 1;
for (int j = 0; j <= M; j++)
{
color[j] = 0;
}
}
return ans;
}
int entast = 1;
for (int i = 1; i < N; i++)
{
if(P[i] != i - 1)
entast = 0;
}
if(entast)
{
int gt = 0;
for (int i = N - 1; i > 0; i--)
{
if(C[i] != C[i - 1])
{
gt = i - 1;
break;
}
}
for (int i = gt; i < N; i++)
{
ans[i] = 1;
}
return ans;
}
Dfs1(0);
for(int i = 1; i < N; i++)
{
v[P[i]].push_back({i, C[i]});
}
for (int i = 1; i <= M; i++)
{
zuyg[i] = {-1, -1};
}
for (int i = 1; i < N; i++)
{
if(zuyg[C[i]].first == -1)
{
zuyg[C[i]].first = P[i];
}
else
zuyg[C[i]].second = P[i];
}
for (int i = 1; i <= M; i++)
{
if(zuyg[i].first != -1)
{
if(zuyg[i].second != -1)
{
if(zuyg[i].first == zuyg[i].second)
{
han[zuyg[i].first]++;
}
else if(stug(zuyg[i].first, zuyg[i].second))
{
gag[zuyg[i].first]+=2;
han[zuyg[i].first]++;
gag[zuyg[i].second]++;
han[zuyg[i].second]++;
}
else if(stug(zuyg[i].second, zuyg[i].first))
{
gag[zuyg[i].first]++;
han[zuyg[i].first]++;
gag[zuyg[i].second]+=2;
han[zuyg[i].second]++;
}
else
{
gag[zuyg[i].first]++;
han[zuyg[i].first]++;
gag[zuyg[i].second]++;
han[zuyg[i].second]++;
}
}
else
{
gag[zuyg[i].first]++;
han[zuyg[i].first]++;
}
}
}
Dfs2(0);
for (int i = 0; i < N; i++)
{
if(gag[i] - han[i] >= 0)
{
ans[i] = 1;
}
}
return ans;
}
