#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 1;
vector <int> adj[maxn];
int grps[maxn][2];
int col[maxn];
int depth[maxn];
void dfs(int s, int d) {
depth[s] = d;
grps[d][col[s]]++;
for (auto i : adj[s])
dfs(i, d+1);
}
pair <int, int> get_best(pair <int, int> a, pair <int, int> b) {
if (a.first > b.first)
return a;
if (b.first > a.first)
return b;
if (a.second < b.second)
return a;
return b;
}
vector <pair <int, int>> f;
void dfs2(int s, int c) {
if (col[s] == c)
f[depth[s]].first++;
f[depth[s]+1].second += (int)adj[s].size();
for (auto i : adj[s])
dfs2(i, c);
}
vector <int> nodes;
void dfs3(int s) {
if (col[s] != col[0]) {
nodes.push_back(s);
return;
}
for (auto i : adj[s])
dfs3(i);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, k;
cin >> n >> k;
for (int i = 0; i < n; i++)
cin >> col[i];
for (int i = 1; i < n; i++) {
int p;
cin >> p;
adj[p].push_back(i);
}
dfs(0, 0);
pair <int, int> ans = {0, 0};
for (int i = 0; i < 1; i++) {
// set i as the head
f.clear();
f.resize(n+2);
dfs2(i, col[i]);
pair <int, int> tp = {1, 0};
for (int d = depth[i]+1; d < n; d++) {
tp.first += f[d].first;
if (grps[d][col[i]] > f[d].first) {
int extra = min(grps[d][col[i]] - f[d].first, f[d].second - f[d].first);
tp.first += extra;
tp.second += extra;
}
}
ans = get_best(ans, tp);
}
dfs3(0);
for (auto i : nodes) {
// set i as the head
f.clear();
f.resize(n+2);
dfs2(i, col[i]);
pair <int, int> tp = {1, 0};
for (int d = depth[i]+1; d < n; d++) {
if (f[d].second == 0)
break;
tp.first += f[d].first;
if (grps[d][col[i]] > f[d].first) {
int extra = min(grps[d][col[i]] - f[d].first, f[d].second - f[d].first);
tp.first += extra;
tp.second += extra;
}
}
ans = get_best(ans, tp);
}
cout << ans.first << ' ' << ans.second << '\n';
}
# | 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... |