제출 #1324244

#제출 시각아이디문제언어결과실행 시간메모리
1324244boclobanchatCat in a tree (BOI17_catinatree)C++20
100 / 100
126 ms34876 KiB
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+5;
priority_queue< int,vector<int>,greater<int> > pq[MAXN];
vector<int> ds[MAXN];
void dfs(int i,int pre,int d)
{
	pq[i].push(0);
	for(auto v:ds[i]) if(v!=pre)
	{
		dfs(v,i,d);
		while(!pq[v].empty()) pq[i].push(pq[v].top()+1),pq[v].pop();
	}
	while(true)
	{
		int a=pq[i].top();
		pq[i].pop();
		if(pq[i].empty())
		{
			pq[i].push(a);
			break;
		}
		int b=pq[i].top();
		if(a+b<d) continue;
		pq[i].push(a);
		break;
	}
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,d;
    cin>>n>>d;
    for(int i=1;i<n;i++)
    {
    	int pre;
    	cin>>pre;
    	ds[pre].push_back(i);
	}
	dfs(0,0,d);
	int ans=0;
	while(!pq[0].empty()) pq[0].pop(),ans++;
	cout<<ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...