#include "beechtree.h"
#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
using ld = long double;
//#define int ll
#define sz(x) ((int)(x).size())
using pii = pair<int,int>;
using tii = tuple<int,int,int>;
const int nmax = 3e5 + 5;
const int mod = 998244853;
struct Mint {
int val;
Mint(ll x = 0): val((x % mod + mod) % mod) {;}
Mint operator +(const Mint& x) const { return Mint(val + x.val); }
Mint operator -(const Mint& x) const { return Mint(val - x.val); }
Mint operator *(const Mint& x) const { return Mint((ll)val * x.val); }
Mint operator +=(const Mint& x) { return *this = Mint(val + x.val); }
Mint operator -=(const Mint& x) { return *this = Mint(val - x.val); }
Mint operator *=(const Mint& x) { return *this = Mint((ll)val * x.val); }
Mint operator ^(const int& _b) const {
Mint accum = 1, a = *this;
int b = _b;
while(b) {
accum = (b & 1? accum * a : accum);
a *= a;
b >>= 1;
}
return accum;
}
Mint operator /(const Mint& x) { return Mint((ll)val * (x ^ (mod - 2)).val); }
Mint operator /=(const Mint& x) { return *this = Mint((ll)val * (x ^ (mod - 2)).val); }
};
Mint p[2][nmax];
#define hash bjsefdjhsdsfhoi
struct hash {
Mint v[2];
int len;
hash(Mint a = 0, Mint b = 0, int c = 0) { v[0] = a; v[1] = b; len = c; }
hash operator +(const hash& x) const {
return hash(v[0] * p[0][x.len] + x.v[0], v[1] * p[1][x.len] + x.v[1], len + x.len);
}
hash operator -(const hash& x) const {
return hash(v[0] - p[0][len - x.len] * x.v[0], v[1] - p[1][len - x.len] * x.v[1], len - x.len);
}
bool operator !=(const hash& x) const {
return v[0].val != x.v[0].val || v[1].val != x.v[1].val || len != x.len;
}
ll operator()() const { return (ll)v[0].val * mod + v[1].val; }
};
vector<pii> g[nmax];
vector<pii> invg[nmax];
vector<int> P, C;
bool isanc(unordered_set<int>& A, unordered_set<int>& B) {
if(sz(A) < sz(B)) return 0;
for(auto &x : B)
if(!A.count(x)) return 0;
return 1;
}
vector<int> sol;
int h[nmax];
int area[nmax], pin[nmax], pout[nmax], inp;
hash subarb[nmax];
bool superimposable(int x, int y) { // x peste y
if(sz(g[x]) == 0 || x == y) return 1;
if(area[x] == area[y] && subarb[x]() == subarb[y]()) return 1;
if(pin[y] <= pin[x] && pout[x] <= pout[y] && sol[y]) return 1;
//if(calc[x][y]) return SI[x][y];
//calc[x][y] = 1;
//SI[x][y] = 1;
for(auto [a, c] : g[x]) {
auto it = lower_bound(all(invg[y]), pii{c, -1});
if(it == end(invg[y]) || it -> first != c) { return 0; }
if(!superimposable(a, it -> second)) { return 0; }
}
return 1;
}
void insert(int& works, map<int, int>& st, int node) {
if(!works) return;
auto it = st.upper_bound(area[node]);
if(it == st.end());
else if(!superimposable(node, it -> second)) { works = 0; return; }
if(it == st.begin());
else if(!superimposable(prev(it) -> second, node)) { works = 0; return; }
st[area[node]] = node;
return;
}
map<int, int> dfs(int node) {
pin[node] = inp++;
map<int, int> here;
sol[node] = 1;
area[node] = 1;
vector<hash> fils;
unordered_set<int> pula;
for(auto [x, c] : g[node]) {
pula.insert(c);
auto T = dfs(x);
//fils.emplace_back(hash(c) + subarb[x]);
area[node] += area[x];
sol[node] &= sol[x];
if(sz(T) > sz(here)) swap(here, T);
for(auto [a, x] : T) insert(sol[node], here, x);
}
//sort(all(fils), [&](auto a, auto b) { return a() < b(); });
subarb[node] = hash(node);
//for(auto x : fils) subarb[node] = subarb[node] + x;
//subarb[node] = subarb[node] + hash(12);
insert(sol[node], here, node);
pout[node] = inp++;
if(sz(g[node]) != sz(pula)) sol[node] = 0;
return here;
}
std::vector<int> beechtree(int N, int M, std::vector<int> P_, std::vector<int> C_) {
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
p[0][0] = p[1][0] = 1;
p[0][1] = rng() % (mod - 1000) + 503;
p[1][1] = rng() % (mod - 1200) + 505;
for(int i = 2; i < nmax; i++)
p[0][i] = p[0][i - 1] * p[0][1],
p[1][i] = p[1][i - 1] * p[1][1];
P = P_;
C = C_;
for(int i = 1; i < N; i++) {
g[P[i]].emplace_back(i, C[i]);
invg[P[i]].emplace_back(C[i], i);
}
for(int i = 0; i < N; i++) sort(all(invg[i]));
sol.assign(N, 0);
dfs(0);
return sol;
}
/**
Töte es durch genaue Untersuchung\Töte es kann es nur noch schlimmer machen\Es lässt es irgendwie atmen
--
*/
