#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vi vector<int>
#define vl vector<ll>
#define mp make_pair
#define pb push_back
using namespace std;
int n, d;
vi G[200050];
int furthest(int start){
queue<pii> q;
q.push(mp(start, 0));
bool vis[n];
memset(vis, false, sizeof(vis));
vis[start] = true;
int sz = 0, id = 0;
while(!q.empty()){
pii state = q.front(); q.pop();
int at = state.first;
int path = state.second;
if(path > sz){
path = sz;
id = at;
}
for(auto next : G[at]){
if(!vis[next]){
vis[next] = true;
q.push(mp(next, path + 1));
}
}
}
return id;
}
int main(){
cin>>n>>d;
for(int i = 1; i < n; i++){
int x;
cin>>x;
G[x].pb(i);
G[i].pb(x);
}
int one = furthest(0);
int two = furthest(one);
queue<pii> q;
q.push(mp(one, 0));
bool vis[n];
memset(vis, false, sizeof(vis));
vis[one] = true;
int rez = 1;
while(!q.empty()){
pii state = q.front();
q.pop();
int at = state.first;
int path = state.second;
if(path == d){
rez++;
path = 0;
}
for(auto next : G[at]){
if(!vis[next]){
vis[next] = true;
q.push(mp(next, path+1));
}
}
}
cout<<rez<<endl;
}
Compilation message
catinatree.cpp: In function 'int main()':
catinatree.cpp:45:6: warning: unused variable 'two' [-Wunused-variable]
45 | int two = furthest(one);
| ^~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |