#include <bits/stdc++.h>
using namespace std;
typedef int ll;
typedef pair<int,int> pi;
const int MAXN = 100005;
int n, k, label = 0;
int blk = 316;
int color[MAXN], par[MAXN], in[MAXN], out[MAXN], cnt[MAXN], dep[MAXN];
int big[MAXN];
vector<int> adj[MAXN], nodelist[MAXN];
vector<int> deplist[MAXN]; // for each color, record all depths (later sorted & uniqued)
// We'll store frequency maps as sorted vectors of (key, count) pairs.
vector<pi> dp[MAXN], dp2[MAXN], dp3[MAXN], dp4[MAXN], dp5[MAXN];
// For each color (0<=c<k) store the global frequency of nodes of that color by depth.
vector<vector<pi>> colMapVec; // size = k, indexed by color
// The final answer is stored as (res, -swaps) so that max() gives lex–order.
pi ans = { -1000000000, -1000000000 };
// ----- Helper routines for “dp” vectors (sorted by key) -----
// Binary search for key in sorted vector "vec"; returns count if found, else 0.
inline int getValue(const vector<pi>& vec, int key) {
int lo = 0, hi = (int)vec.size()-1;
while(lo <= hi) {
int mid = (lo+hi)/2;
if(vec[mid].first == key)
return vec[mid].second;
else if(vec[mid].first < key)
lo = mid+1;
else
hi = mid-1;
}
return 0;
}
// Insert or update key in sorted vector "vec" by adding "val".
inline void addValue(vector<pi>& vec, int key, int val) {
auto it = std::lower_bound(vec.begin(), vec.end(), make_pair(key,0));
if(it != vec.end() && it->first == key)
it->second += val;
else
vec.insert(it, {key, val});
}
// Merge two sorted vectors (dest and src) summing counts for equal keys.
inline void mergeSortedVectors(vector<pi>& dest, const vector<pi>& src) {
vector<pi> merged;
merged.reserve(dest.size() + src.size());
int i = 0, j = 0;
while(i < dest.size() && j < src.size()){
if(dest[i].first == src[j].first){
merged.push_back({dest[i].first, dest[i].second + src[j].second});
i++; j++;
}
else if(dest[i].first < src[j].first){
merged.push_back(dest[i]);
i++;
}
else {
merged.push_back(src[j]);
j++;
}
}
while(i < dest.size()){
merged.push_back(dest[i]);
i++;
}
while(j < src.size()){
merged.push_back(src[j]);
j++;
}
dest = move(merged);
}
// ----- DFS 1: Euler Tour + depth computation; record each node’s depth in deplist[color] -----
void precomp1(int x = 0) {
in[x] = ++label;
for (int u: adj[x]) {
dep[u] = dep[x] + 1;
precomp1(u);
}
out[x] = label;
deplist[color[x]].push_back(dep[x]);
}
// ----- DFS 2: DSU on tree for "dp" arrays; also build dp2 for later use for small colors -----
void precomp2(int x = 0) {
// Update global frequency for this node’s color.
addValue(colMapVec[color[x]], dep[x], 1);
for (int u: adj[x]) {
precomp2(u);
// Merge dp[u] into dp[x] (small-to–large merging)
if(dp[x].size() < dp[u].size())
swap(dp[x], dp[u]);
mergeSortedVectors(dp[x], dp[u]);
dp[u].clear();
}
addValue(dp[x], dep[x], 1);
// Build dp2[x] for nodes whose color is “small”
if (!big[color[x]]) {
for (int d: deplist[color[x]]) {
int val = getValue(dp[x], d);
if(val)
addValue(dp2[x], d, val);
}
}
}
// ----- DFS for “big” colors: merge dp4 and dp5 arrays -----
void dfs(int x, int c, int yes = 1) {
for (int u: adj[x]) {
dfs(u, c, yes & (color[x] != c));
if(dp4[x].size() < dp4[u].size())
swap(dp4[x], dp4[u]);
mergeSortedVectors(dp4[x], dp4[u]);
if(dp5[x].size() < dp5[u].size())
swap(dp5[x], dp5[u]);
mergeSortedVectors(dp5[x], dp5[u]);
dp4[u].clear(); dp5[u].clear();
}
if(yes && color[x] == c) {
int res = 0, res2 = 0;
// For every depth (from the unique depths for color c) that is deeper than dep[x]
for (int d: deplist[c]) {
if(d <= dep[x])
continue;
int a = getValue(dp4[x], d);
int b = getValue(colMapVec[c], d);
int take = min(a, b);
res += take;
int cval = getValue(dp5[x], d);
res2 += max(0, take - cval);
}
ans = max(ans, make_pair(res, -res2));
}
addValue(dp4[x], dep[x], 1);
if(c == color[x])
addValue(dp5[x], dep[x], 1);
}
// ----- Process “small” colors (those with cnt <= blk) -----
void solve(int c) {
int sz = nodelist[c].size();
// For every pair of nodes of color c where one is an ancestor of the other,
// update dp3 for the ancestor.
for (int i = 0; i < sz; i++){
int x = nodelist[c][i];
for (int j = i+1; j < sz; j++){
int y = nodelist[c][j];
if(in[x] > in[y])
swap(x,y);
if(in[x] <= in[y] && in[y] <= out[x])
addValue(dp3[x], dep[y], 1);
}
}
// Then for each node of color c, use its dp2 and dp3 to compute candidate answer.
for (int i = 0; i < sz; i++){
int x = nodelist[c][i];
int res = 0, res2 = 0;
for (int d: deplist[c]){
if(d <= dep[x])
continue;
int a = getValue(dp2[x], d);
int b = getValue(colMapVec[c], d);
int take = min(a, b);
res += take;
int cval = getValue(dp3[x], d);
res2 += max(0, take - cval);
}
dp2[x].clear(); dp3[x].clear();
ans = max(ans, make_pair(res, -res2));
}
}
// ----- Main -----
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> k;
// Initialize colMapVec so that colMapVec[c] will hold frequency (by depth) for color c.
colMapVec.resize(k);
for (int i = 0; i < n; i++){
cin >> color[i];
cnt[color[i]]++;
nodelist[color[i]].push_back(i);
}
for (int i = 0; i < k; i++){
if(cnt[i] > blk)
big[i] = 1;
}
for (int i = 1; i < n; i++){
cin >> par[i];
adj[par[i]].push_back(i);
}
precomp1();
// For each color, sort and unique the list of depths (to drive our loops later)
for (int i = 0; i < k; i++){
sort(deplist[i].begin(), deplist[i].end());
deplist[i].erase(unique(deplist[i].begin(), deplist[i].end()), deplist[i].end());
}
precomp2();
// Process each color: use DFS for big colors and a different method for small colors.
for (int i = 0; i < k; i++){
if(big[i]){
for (int j = 0; j < n; j++){
dp5[j].clear();
dp4[j].clear();
}
dfs(0, i, 1);
}
else {
solve(i);
}
}
cout << ans.first + 1 << " " << -ans.second << "\n";
return 0;
}
