Submission #43506283

---

Source Code Expand

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define op(x) ((x&1)?x+1:x-1)
#define odd(x) (x&1)
#define even(x) (!odd(x))
#define lc(x) (x<<1)
#define rc(x) (lc(x)|1)
#define lowbit(x) (x&-x)
#define mp(x,y) make_pair(x,y)
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
using namespace std;
const int MAXN = 2e5+10;

typedef vector<int> vec;

int n;
vec e[MAXN],S1,S2;

int fa[MAXN],dep[MAXN],tag[MAXN],rcnt[MAXN],cnt[MAXN],ans;

int vis[MAXN];

void dfs(int u){
	for(auto v:e[u])if(v!=fa[u]){
		dep[v]=dep[u]^1;
		dfs(v);
		cnt[u]++;
	}
	rcnt[u] = cnt[u];
}

struct DSU{
	int p[MAXN];
	void init(){
		iota(p+1,p+1+n,1);
	}
	int find(int x){
		return (x == p[x]) ? (x) : (p[x] = find(p[x]));
	}
	void rst(int x,int md=0){
		if(md)p[x] = find(fa[x]);
		else p[x] = find(fa[fa[x]]);
	}
}dsu;

set<int>son[MAXN];

int sz[MAXN],dfn[MAXN],dtot;

struct BIT{
	int t[MAXN];
	void mdf(int x,int v){
		for(;x<=dtot;x+=lowbit(x))t[x] += v;
	}
	int qry(int x,int S=0){
		for(;x;x-=lowbit(x))S+=t[x];
		return S;
	}
}bit,bit2;
int qry(int x){
	if(x==0)return bit.qry(dtot);

	return bit.qry(dfn[x] + sz[x]-1) - bit.qry(dfn[x]-1);
}
int qry2(int x){
	if(x==0)return bit2.qry(dtot);

	return bit2.qry(dfn[x] + sz[x]-1) - bit2.qry(dfn[x]-1);
}

vector<int>tmp;

void dfs2(int u){
	sz[u]=1;
	dfn[u] = ++dtot;
	for(auto v:e[u])if(v!=fa[u] && !vis[v])dfs2(v),sz[u]+=sz[v],son[u].insert(v);
}

struct comp{
	bool operator()(int x,int y)const{
		return (sz[x] != sz[y]) ? (sz[x] < sz[y]) : (x < y);
	}
};
set<int,comp>S;

int ban[MAXN];

int main(){
	ios::sync_with_stdio(false);

	cin>>n;
	rep(i,2,n){
		cin>>fa[i];
		e[fa[i]].push_back(i);
	}

	dfs(1);

	rep(i,1,n)if(!rcnt[i]){
		if(!dep[i])S1.push_back(i);
		else{
			cnt[fa[i]]--;
			if(cnt[fa[i]])S2.push_back(i);
		}
	}

	int t = 0;
	for(;S1.size() || S2.size();t^=1){
		if(S1.size()){
			int u = S1.back();S1.pop_back();vis[u]=1;	
			ans += (!t);
			int p = fa[u];
			cnt[p]--;
			if(!cnt[p]){
				cnt[fa[p]]--;
				if(cnt[fa[p]])S2.push_back(p);
			}
		}else{
			int u = S2.back();S2.pop_back();vis[u]=1;
			ans += t;
		}
	}

	if(vis[1]){
		cout<<ans<<endl;
		exit(0);
	}


	int num = 0;
	rep(i,1,n)if(!vis[i])num++;

	//
	dfs2(1);sz[0] = sz[1];

	dsu.init();
	rep(i,1,n)if(!vis[i] && !dep[i] && son[i].size() == 1)dsu.rst(i,1);

	rep(i,1,n)if(!vis[i] && dep[i] && son[fa[i]].size() == 1)dsu.rst(i);

	rep(i,1,n)if(son[i].empty() && !vis[i]){
		tmp.push_back(dsu.find(i));
	}
	sort(tmp.begin(),tmp.end(),[&](int x,int y){return dfn[x] > dfn[y];});

	for(auto u:tmp){
		if(!qry2(u)){
			if(u)bit2.mdf(dfn[u],1);

			S.insert(u);
		}
	}

	for(;S.size();t^=1){
		int u = *S.begin();S.erase(u);

		int val = sz[u];

		ans += val * t;

		if(!u)break;
		bit.mdf(dfn[u],val);
		bit2.mdf(dfn[u],-1);

		son[fa[u]].erase(u);
		assert(son[fa[u]].size());
		if(son[fa[u]].size() == 1){
			int p = *son[fa[u]].begin();
			dsu.rst(p);dsu.rst(fa[p]);
			if(S.find(p) != S.end()){
				S.erase(p);

				bit2.mdf(dfn[p],-1);

				int to = dsu.find(p);

				assert(S.find(to) == S.end());
				if(!qry2(to)){
					sz[to] -= qry(to);

					if(to)bit2.mdf(dfn[to],1);
					S.insert(to);
				}
			}
		}
	}

	cout<<ans<<endl;
    return 0;
}

Submission Info

Judge Result