#include <bits/stdc++.h>
typedef int ll;
#define FOR(i,x,y) for(ll i=x; i<y; i++)
#define FORNEG(i,x,y) for(ll i=x; i>y; i--)
using namespace std;
vector<basic_string<ll>> edges;
vector<ll> pref;
ll n,k;
ll timer = 0;
ll tin[100005];
ll tout[100005];
ll depth[100005];
unordered_map<ll, ll> stuff[100005];
vector<ll> depths[100005];
vector<ll> consider;
vector<ll> prefs[100005];
ll ans = -1, ans2 = 0;
void dfs(ll a, ll d){
depths[d].push_back(a);
depth[a] = d;
stuff[d][pref[a]] += 1;
tin[a] = timer;
timer += 1;
for (auto&i : edges[a]){
dfs(i, d+1);
}
tout[a] = timer;
}
ll numchild(ll a, ll k){
if (!(0<=k && k<100005)) return 0;
vector<ll> &sus = depths[k];
if (sus.size()==0) return 0;
if (depth[a] == k) return 0;
ll lo = 0;
ll hi = sus.size()-1;
while (lo<hi){
ll mid = (lo+hi)/2;
if (tin[sus[mid]] >= tin[a]) hi = mid;
else lo = mid+1;
}
ll leftp = lo;
lo = 0;
hi = sus.size()-1;
while (lo<hi){
ll mid = (lo+hi+1)/2;
if (tout[sus[mid]] <= tout[a]) lo = mid;
else hi = mid-1;
}
ll rightp = lo;
if (!(tin[a] <= tin[sus[leftp]] && tout[sus[leftp]] <= tout[a])) return 0;
return max((ll)0,rightp-leftp+1);
}
ll numspecialchild(ll a, ll k, ll c){
if (!(0<=k && k<100005)) return 0;
vector<ll> &sus = depths[k];
if (sus.size()==0) return 0;
if (depth[a] == k) return 0;
ll lo = 0;
ll hi = sus.size()-1;
while (lo<hi){
ll mid = (lo+hi)/2;
if (tin[sus[mid]] >= tin[a]) hi = mid;
else lo = mid+1;
}
ll leftp = lo;
lo = 0;
hi = sus.size()-1;
while (lo<hi){
ll mid = (lo+hi+1)/2;
if (tout[sus[mid]] <= tout[a]) lo = mid;
else hi = mid-1;
}
ll rightp = lo;
ll ans = 0;
if (!(tin[a] <= tin[sus[leftp]] && tout[sus[leftp]] <= tout[a])) return 0;
FOR(i,leftp, rightp+1){
ans += (pref[sus[i]]==c);
}
return ans;
}
void solve(ll a){
ll tans = 1;
ll tans2 = 0;
for (auto&i : consider){
ll temp = numchild(a,i);
if (temp==0) continue;
tans += min(temp, stuff[i][pref[a]]);
tans2 += min(temp, stuff[i][pref[a]]) - numspecialchild(a, i, pref[a]);
}
if (tans > ans) ans = tans, ans2 = tans2;
else if (tans == ans) ans2 = min(ans2, tans2);
}
void solve2(ll a){
ll tans = 1;
ll tans2 = 0;
FOR(i, depth[a]+1, n){
ll temp = numchild(a,i);
if (temp==0) break;
tans += min(temp, stuff[i][pref[a]]);
tans2 += min(temp, stuff[i][pref[a]]) - numspecialchild(a, i, pref[a]);
}
if (tans > ans) ans = tans, ans2 = tans2;
else if (tans == ans) ans2 = min(ans2, tans2);
}
void dfs2(ll a, ll p){
if(pref[a] == p){
solve2(a);
return;
}
for (auto& i :edges[a]) dfs2(i,p);
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> k;
FOR(i,0,n) edges.push_back({}), pref.push_back(0);
FOR(i,0,n){
cin >> pref[i];
prefs[pref[i]].push_back(i);
}
FOR(i,1,n){
ll temp;
cin >> temp;
edges[temp].push_back(i);
}
dfs(0,0);
FOR(p,0,k){
if (prefs[p].size() > 400) dfs2(0,p);
else{
consider.clear();
unordered_set<ll> temps;
for (auto&i : prefs[p]) temps.insert(depth[i]);
for (auto&i : temps)consider.push_back(i);
for (auto&i : prefs[p]){
solve(i);
}
}
}
cout << ans << " " << ans2 << endl;
}
# | 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... |