#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, S = 350;
int n, k, a[N], ans, mi, occur[N], C[N], h[N];
vector<int> child[N];
set<int> vec[N];
map<int, int> cnt[N];
void bfs(int v)
{
queue<int> Q;
Q.push(v);
int X = 0;
while(Q.size())
{
int u = Q.front();
Q.pop();
X += (a[v] == a[u]);
C[h[u]]++;
for(int c : child[u])
Q.push(c);
}
int sol = 0;
for(int i = h[v]; C[i] > 0; i++)
{
sol += min(C[i], cnt[a[v]][i]);
C[i] = 0;
}
if(sol > ans)
ans = sol, mi = sol - X;
else if(sol == ans)
mi = min(sol - X, mi);
}
void dfs(int v, int color)
{
if(a[v] == color)
{
bfs(v);
return;
}
for(int c : child[v])
dfs(c, color);
}
void prejob(int v)
{
vec[a[v]].insert(h[v]);
cnt[a[v]][h[v]] ++;
for(int c : child[v])
{
h[c] = h[v] + 1;
prejob(c);
}
}
int cc[N];
void dfs2(int v)
{
vector<int> sz;
int X = cc[a[v]];
if(h[v] == *vec[a[v]].begin())
{
for(int hv : vec[a[v]])
sz.push_back(C[hv]);
}
cc[a[v]]++;
C[h[v]]++;
for(int c : child[v])
dfs2(c);
X = cc[a[v]] - X;
if(h[v] == *vec[a[v]].begin())
{
int i = 0;
int sol = 0;
for(int hv : vec[a[v]])
if(hv >= h[v])
{
sol += min(C[hv] - sz[i], cnt[a[v]][hv]);
i++;
}
if(sol > ans)
ans = sol, mi = sol - X;
else if(sol == ans)
mi = min(mi, sol - X);
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n >> k;
for(int i = 0; i < n; i ++)
{
cin >> a[i];
occur[a[i]]++;
}
cnt[a[0]][0]++;
for(int i = 1; i < n; i ++)
{
int p;
cin >> p;
child[p].push_back(i);
}
prejob(0);
for(int i = 0; i < k; i ++)
if(occur[i] >= S)
dfs(0, i);
if(ans < S)
dfs2(0);
cout << ans << ' ' << mi << endl;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |