제출 #440945

#제출 시각아이디문제언어결과실행 시간메모리
440945S2speedCat in a tree (BOI17_catinatree)C++17
100 / 100
131 ms23472 KiB
#include<bits/stdc++.h>

using namespace std;

#define all(x) x.begin() , x.end()
#define sze(x) (ll)(x.size())
typedef long long ll;
typedef pair<ll , ll> pll;
typedef pair<int , int> pii;
typedef pair<pll , bool> pllb;

const ll maxn = 2e5 + 16 , md = 1e9 + 7;

ll tav(ll n , ll k){
	ll res = 1;
	while(k > 0){
		if(k & 1){
			res *= n; res %= md;
		}
		n *= n; n %= md;
		k >>= 1;
	}
	return res;
}
 
ll n , d , sq = 300;
ll par[maxn] , dis[maxn] , cl[maxn] , ds[maxn];
vector<pll> u;
bitset<maxn> far;
vector<ll> bfs , adj[maxn];

void BFS(ll r){
	ds[r] = 0;
	bfs.push_back(r);
	ll x = 0;
	while(x < sze(bfs)){
		ll v = bfs[x++];
		if(ds[v] == d - 1) break;
		for(auto i : adj[v]){
			if(ds[i] > ds[v] + 1){
				ds[i] = ds[v] + 1;
				bfs.push_back(i);
				far[i] = false;
			}
		}
	}
	bfs.clear();
	return;
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	memset(cl , 63 , sizeof(cl));
	par[0] = -1; dis[0] = 0;
	cin>>n>>d;
	u.push_back({0 , 0});
	for(ll i = 1 ; i < n ; i++){
		cin>>par[i];
		dis[i] = dis[par[i]] + 1;
		u.push_back({dis[i] , i});
	}
	sort(all(u) , greater<pll>());
	ll ans = 0 , lm = (d - 1) >> 1;
	if(d < sq){
		for(ll e = 0 ; e < n ; e++){
			ll i = u[e].second , v = i;
			bool ch = true;
			for(ll j = 0 ; j <= lm && v != -1 ; j++){
				ch &= (cl[v] + j >= d);
				v = par[v];
			}
			if(!ch) continue;
			ans++;
			v = par[i];
			for(ll j = 1 ; j < d && v != -1 ; j++){
				cl[v] = j;
				v = par[v];
			}
		}
		cout<<ans<<'\n';
		return 0;
	}
	far.set();
	memset(ds , 63 , sizeof(ds));
	for(ll i = 1 ; i < n ; i++){
		adj[i].push_back(par[i]);
		adj[par[i]].push_back(i);
	}
	for(ll e = 0 ; e < n ; e++){
		ll i = u[e].second;
		if(far[i]){
			ans++;
			BFS(i);
		}
	}
	cout<<ans<<'\n';
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...