Submission #1695746

---

Source Code Expand

#include <bits/stdc++.h>
#define long long long
#define up(i,a,b) for (int i=a; i<=b; i++)
#define down(i,a,b) for (int i=a; i>=b; i--)
#define endl '\n'
#define X first
#define Y second
#define II pair<int, int>
#define III pair<int, pair<int, int> >
#define debug(X) cerr<< #X << " = " <<X << endl
#define debug2(X,Y) cerr<< #X << " = " <<X << ","<<#Y<<" = "<<Y<<endl
#define show(X,a,b) {cerr << #X << " = "; up(__,a,b) cerr << X[__] << ' '; cerr << endl;}
#define gc getchar
#define pc putchar
using namespace std;

inline void read(int &x)
{
    register int c = gc();
    x = 0;
    int neg = 0;
    for (;((c<48 || c>57) && c != '-') ;c = gc());
    if(c=='-') {neg=1;c=gc();}
    for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
    if(neg) x=-x;
}
inline void writeln(int x){

         char buffor[21];
         register int i=0;
         int neg=0; if (x<0) {neg=1; x= -x;}
         do{
               buffor[i++]=(x%10)+'0';
               x/=10;
            } while(x);
           i--;
           if (neg) pc('-');
           while(i>=0) pc(buffor[i--]);
           pc('\n');
       }

const int N= (int)1e5+10;
int n,K;
vector<int> a[N];
int p[18][N],h[N],listH[N],in[N],out[N],Time;
int res= 0;
struct segment_tree
{
	int low[4*N],high[4*N],it[4*N];
	void build(int x,int l,int r)
	{
        low[x]= l; high[x]= r; it[x]= 0;
        if (l==r) return;
        int m= (l+r)/2;
        build(2*x,l,m); build(2*x+1,m+1,r);
	}

	void update(int x,int l,int r)
	{
        if (low[x]> r or high[x]<l) return;
        if (low[x]>=l and high[x]<=r)
		{
			it[x]++; return;
		};
        update(2*x,l,r); update(2*x+1,l,r);
	}
	int query(int x,int pos)
	{
        if (low[x]== high[x]) return it[x];
        if (pos<= high[2*x]) return it[x]+ query(2*x,pos);
        else return it[x]+ query(2*x+1,pos);
	}
}exist;
void input()
{
    cin>>n>>K;
    up(i,1,n)
    {
        if (i==1)
		{
			int u; cin>>u; if (u!=1) res++;
		}
		else
		{
			cin>>p[0][i];
			a[p[0][i]].push_back(i);
		}
    }
}

void dfs(int u,int par,int curH)
{
	p[0][u]= par; h[u]= curH;
	in[u]= ++Time;
	for (auto v: a[u])
		if (v!= par) dfs(v,u,curH+1);
	out[u]= Time;
}
bool byH(int i,int j)
{
	return h[i]> h[j];
}
int getbit(int x,int k)
{
	return (x>>k) & 1;
}
int par_k(int u)
{
	down(i,17,0)
	 if (getbit(K-1,i)) u= p[i][u];
	return u;
}
void solve()
{
    Time= 0; dfs(1,0,0);
    up(i,1,17)
     up(j,1,n)
      p[i][j]= p[i-1][p[i-1][j]];
    up(i,1,n) listH[i]= i;
    sort(listH+1,listH+1+n,byH);

    exist.build(1,1,n);
    up(id,1,n)
    {
    	int u= listH[id];
        if (h[u]<=K or exist.query(1,in[u])!=0 ) continue;
        int p= par_k(u);
        exist.update(1,in[p],out[p]); res++;
    }

    cout<<res;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);// don't use when interactive

    #ifdef I_Love_Pork
    #define TASK "tmp"
    freopen(TASK".inp","r",stdin);
    freopen(TASK".out","w",stdout);
	#endif

    input();
    solve();

    return 0;
}

Submission Info

Judge Result