You cannot select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
77 lines
2.3 KiB
C++
77 lines
2.3 KiB
C++
#define _CRT_SECURE_NO_WARNINGS
|
|
#define _SILENCE_CXX17_C_HEADER_DEPRECATION_WARNING
|
|
#include <bits/stdc++.h>
|
|
using namespace std;
|
|
const int N = 1e5 + 50;
|
|
int cnt[N], w[N], nx[N], adj[N], que[N], ans[N], fa[N], dep[N];
|
|
bool vis[N];
|
|
int main()
|
|
{
|
|
set<int> s1, s2;
|
|
for (int n; ~scanf("%d", &n);)
|
|
{
|
|
memset(cnt, 0, sizeof cnt);
|
|
memset(ans, 0, sizeof ans);
|
|
memset(vis, 0, sizeof vis);
|
|
memset(adj, 0, sizeof adj);
|
|
for (int i = 2; i <= n; i++)
|
|
{
|
|
scanf("%d", &fa[i]);
|
|
nx[i] = adj[fa[i]];
|
|
adj[fa[i]] = i;
|
|
}
|
|
for (int i = 1; i <= n; i++)
|
|
{
|
|
scanf("%d", w + i);
|
|
cnt[w[i]]++;
|
|
}
|
|
for (int i = 1; i <= n; i++) ans[i] = cnt[w[i]] > 1;
|
|
int h = 0, t = 0;
|
|
for (vis[que[t++] = 1] = true; h ^ t; h++)
|
|
for (int x = adj[que[h]]; x; x = nx[x])
|
|
if (!vis[x])
|
|
vis[que[t++] = x] = true, dep[x] = dep[que[h]] + 1;
|
|
for (int i = t - 1; i; i--)
|
|
ans[fa[que[i]]] += ans[que[i]];
|
|
pair<int, int> ans1{-1, -1}, ans2{-1, -1};
|
|
for (int i = 1; i <= n; i++)
|
|
{
|
|
pair<int, int> cur = {ans[i], i};
|
|
if (ans1 < cur)
|
|
{
|
|
ans2 = ans1;
|
|
ans1 = cur;
|
|
}
|
|
else if (ans2 < cur)
|
|
{
|
|
ans2 = cur;
|
|
}
|
|
}
|
|
memset(vis, 0, sizeof vis);
|
|
h = t = 0;
|
|
que[t++] = dep[ans1.second] > dep[ans2.second] ? ans1.second : ans2.second;
|
|
s1.clear(), s2.clear();
|
|
s1.insert(w[*que]);
|
|
s2.insert(w[1]);
|
|
for (; h ^ t; h++)
|
|
for (int x = adj[que[h]]; x; x = nx[x])
|
|
if (!vis[x])
|
|
{
|
|
s1.insert(w[x]);
|
|
vis[que[t++] = x] = true;
|
|
}
|
|
h = t = 0;
|
|
for (que[t++] = 1; h ^ t; h++)
|
|
for (int x = adj[que[h]]; x; x = nx[x])
|
|
if (!vis[x])
|
|
{
|
|
s2.insert(w[x]);
|
|
vis[que[t++] = x] = true;
|
|
}
|
|
int ans = s1.size() + s2.size();
|
|
printf("%d\n", ans);
|
|
//printf("%d %d %d %d\n", ans1.first, ans1.second, ans2.first, ans2.second);
|
|
}
|
|
return 0;
|
|
}
|