#include"beechtree.h"
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<algorithm>
#define ep emplace
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const int inf=1e9+7;
const ll INF=1e18;
const int mxn=200010;
vector<pi>adj[mxn];
int sz[mxn];
void dfs(int x)
{
sz[x]=1;
for(pi&t:adj[x])
dfs(t.fi),sz[x]+=sz[t.fi];
return;
}
bool isinc(const vector<int>&x,const vector<int>&y)
{
if(x.size()>y.size())
return 0;
for(const int&t:x)
if(!binary_search(all(y),t))
return 0;
return 1;
}
vector<int>subtr[mxn];
multimap<int,int>ss[mxn];
map<int,set<pi> >mm[mxn];
int n,m;
int p[mxn],c[mxn];
vector<vector<int> >st;
bool push(int i,int j)
{
subtr[i].eb(j);
int x=sz[j];
auto&s=ss[i];
{
auto it=s.ep(x,j);
if(it!=s.begin())
{
auto it2=prev(it);
if(!isinc(st[it2->se],st[j]))
return 0;
}
auto it2=next(it);
if(it2!=s.end())
{
if(!isinc(st[j],st[it2->se]))
return 0;
}
}
if(j==0)
return 1;
set<pi>&m=mm[i][c[j]];
int y=sz[p[j]];
{
auto it=m.ep(x,y).fi;
if(it!=m.begin())
{
auto it2=prev(it);
if(it2->se>y||(x!=it2->fi&&y==it2->se))
return 0;
}
auto it2=next(it);
if(it2!=m.end())
{
if(y>it2->se||(x!=it2->fi&&y==it2->se))
return 0;
}
}
return 1;
}
vector<int>beechtree(int N,int M,vector<int>P,vector<int>C)
{
n=N,m=M;
for(int i=0;i<n;i++)
p[i]=P[i],c[i]=C[i];
vector<int>isok(n,1);
for(int i=1;i<n;i++)
adj[p[i]].eb(i,c[i]);
st.resize(n);
for(int i=n;i-->0;)
{
for(pi&t:adj[i])
st[i].eb(t.se);
sort(all(st[i]));
auto it=unique(all(st[i]));
if(it!=st[i].end())
isok[i]=0;
if(isok[i]==0&&i>0)
isok[p[i]]=0;
st[i].eb(inf);
}
dfs(0);
vector<int>vv;
for(int i=0;i<n;i++)
if(isok[i]==1)
vv.eb(i);
sort(all(vv),[&](int x,int y){return sz[x]<sz[y];});
for(int&i:vv)
{
if(isok[i]==0)
{
if(i>0)
isok[p[i]]=0;
continue;
}
for(pi&tt:adj[i])
{
int t=tt.fi;
}
push(i,i);
for(pi&tt:adj[i])
{
int t=tt.fi;
if(subtr[t].size()>subtr[i].size())
swap(subtr[t],subtr[i]),
swap(ss[t],ss[i]),
swap(mm[t],mm[i]);
ss[t].clear();
mm[t].clear();
for(int&x:subtr[t])
{
if(!push(i,x))
{
isok[i]=0;
break;
}
}
subtr[t].clear();
if(isok[i]==0)
break;
}
if(isok[i]==0)
{
if(i>0)
isok[p[i]]=0;
continue;
}
}
return isok;
}
