#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <numeric>
#include <cassert>
#define endl '\n'
#define sp ' '
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int maxn = 2e5+5;
vector<int> adj[maxn];
int height[maxn], firstpos[maxn];
bool visited[maxn];
int n,d;
int start;
int num=0;
void dfs(int v, int depth){
visited[v] = true;
firstpos[v] = num;
height[num] = depth;
num++;
for(int i : adj[v]){
if(!visited[i])
dfs(i,depth+1);
}
}
pii t[4*maxn];
void build(int tl, int tr, int v){
if(tl>tr) return;
if(tl==tr){
t[v].ff = height[tl];
t[v].ss = tl;
return;
}
int tm = (tl+tr)/2;
build(tl,tm,2*v);
build(tm+1,tr,2*v+1);
t[v] = min(t[2*v],t[2*v+1]);
}
pii query(int l, int r, int tl, int tr, int v){
if(tl>r || tr<l || tl>tr) return {1e9,0};
if(tl >= l && tr <= r) return t[v];
int tm = (tl+tr)/2;
return min(query(l,r,tl,tm,2*v), query(l,r,tm+1,tr,2*v+1));
}
void findstart(int fr){
queue<int> q;
q.push(fr);
while(q.size()){
int cur = q.front();q.pop();
visited[cur] = true;
start = cur;
for(int i : adj[cur])
if(!visited[i])
q.push(i);
}
memset(visited,0,sizeof visited);
q.push(start);
while(q.size()){
int cur = q.front();q.pop();
visited[cur] = true;
start = cur;
for(int i : adj[cur])
if(!visited[i])
q.push(i);
}
memset(visited,0,sizeof visited);
}
int ans = 0;
int last = -1;
void bfs(int v){
// start'tan baslayarak depth d den buyuk esit oldugunda boya, her bi dfs icin depthi min(depth, depth[
memset(visited, 0, sizeof visited);
queue<pii> q;
q.push({v,d});
while(q.size()){
int cur = q.front().ff;
int dist = q.front().ss;
q.pop();
visited[cur] = true;
if(last!=-1){
int aa = firstpos[last];
int bb = firstpos[cur];
int calc = height[aa] + height[bb] - 2*height[query(min(aa,bb),max(aa,bb),0,n-1,1).ss];
//cout << height[aa] << sp << height[bb] << endl;
//cout << last << sp << cur << sp << calc << endl;
//cout << "q " << query(min(aa,bb),max(aa,bb),0,n-1,1).ff << endl;
//cerr << aa << sp << bb << endl;
dist = min(dist, calc);
}
bool boya = false;
if(dist >= d){
ans++;
last = cur;
boya = true;
}
for(int i : adj[cur]){
if(!visited[i])
q.emplace(i,(boya?1:dist+1));
}
}
}
int main(){
ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);cerr.tie(nullptr);
cin>>n>>d;
for(int i=1;i<n;i++){
int cur;cin>>cur;
adj[i].pb(cur);
adj[cur].pb(i);
}
findstart(0);
//cerr << start << endl;
dfs(start,0);
//for(int i=0;i<n;i++){
// cerr << i << sp << "h: " << height[i] << sp << "f: " << firstpos[i] << endl;
//}
for(int i=0;i<=4*n;i++) t[i].ff = 1e9;
build(0,n-1,1);
bfs(start);
cout << ans << endl;
//cerr << query(1,1,0,n-1,1).ff << sp << query(1,1,0,n-1,1).ss << endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
5228 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
5228 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
5228 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
