Submission #1840466

---

Source Code Expand

#include <cstdio>
#include <iostream>
#include <algorithm>

using namespace std;

const int N=100010;

int n,k,cnt,ans,t,G[N],dfn[N];
struct edge{
  int t,nx;
}E[N<<1];

inline void addedge(int x,int y){
  E[++cnt].t=y; E[cnt].nx=G[x]; G[x]=cnt;
  E[++cnt].t=x; E[cnt].nx=G[y]; G[y]=cnt;
}

int fa[N][20],dpt[N];

void dfs(int x,int f){
  dfn[x]=++t; fa[x][0]=f; dpt[x]=dpt[f]+1;
  for(int i=1;i<=18;i++) fa[x][i]=fa[fa[x][i-1]][i-1];
  for(int i=G[x];i;i=E[i].nx)
    if(E[i].t!=f) dfs(E[i].t,x);
}

int Q[N],tt;

inline bool cmp(const int &a,const int &b){
  return dfn[a]<dfn[b];
}

inline int lca(int x,int y){
  if(dpt[x]<dpt[y]) swap(x,y);
  for(int i=18;~i;i--)
    if(dpt[fa[x][i]]>=dpt[y]) x=fa[x][i];
  if(x==y) return x;
  for(int i=18;~i;i--)
    if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
  return fa[x][0];
}

int main(){
  scanf("%d%d",&n,&k); ans=0;
  int x; scanf("%d",&x);
  if(x!=1) ans++;
  for(int i=2;i<=n;i++)
    scanf("%d",&x),addedge(x,i);
  dfs(1,0);
  for(int i=1;i<=n;i++)
    if(dpt[i]-1>k) Q[++tt]=i;
  if(!tt) return printf("%d\n",ans),0;
  sort(Q+1,Q+1+tt,cmp); int lst=Q[1]; ans++;
  for(int i=2;i<=tt;i++){
    if(dpt[Q[i]]-dpt[lca(lst,Q[i])]+1>k) ans++,lst=Q[i];
  }
  printf("%d\n",ans);
  return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:45:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&n,&k); ans=0;
                      ^
./Main.cpp:46:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   int x; scanf("%d",&x);
                        ^
./Main.cpp:49:32: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&x),addedge(x,i);
                                ^

Judge Result